Content is user-generated and unverified.

Linear Algebra Algorithms Taxonomy

Based on "Matrix Computations" by Golub & Van Loan and "Numerical Linear Algebra" by Trefethen & Bau

Download Instructions: Copy this entire document and save it as a .md file (e.g., linear_algebra_taxonomy.md)

Code Examples Legend

🐍 Python implementations
💎 Ruby implementations
📚 Educational/tutorial resources
🏭 Production-ready libraries

Basic Vector and Matrix Operations
Linear System Solution Algorithms
Eigenvalue and Singular Value Algorithms
Matrix Decomposition and Factorization
Numerical Linear Algebra Infrastructure
Advanced and Specialized Algorithms
Additional Resources

I. Basic Vector and Matrix Operations

Vector Operations

Algorithm	Description	Python	Ruby
Vector Addition/Subtraction	Element-wise arithmetic	NumPy basics	Ruby Matrix
Scalar-Vector Multiplication	Scaling by constants	NumPy broadcasting	Matrix ops
Dot Product	Inner product x^T y	numpy.dot	NMatrix
Vector Norms	‖x‖₁, ‖x‖₂, ‖x‖∞	numpy.linalg.norm	Numo::Linalg
Cross Product	3D vector x × y	numpy.cross	Vector class
Vector Normalization	Convert to unit length	sklearn.preprocessing	Custom Ruby
Hadamard Product	Element-wise multiplication	NumPy ufuncs	NMatrix element-wise

Matrix-Vector Operations

Algorithm	Description	Python	Ruby
Matrix-Vector Multiplication	Computing Ax	numpy.dot	Matrix multiply
Rank-1 Update	A + uv^T	numpy.outer	Outer product
Outer Product	Form matrix from vectors	numpy.outer	RMatrix

Matrix-Matrix Operations

Algorithm	Description	Python	Ruby
Matrix Addition/Subtraction	Element-wise arithmetic	NumPy operations	Matrix arithmetic
Standard Matrix Multiply	O(n³) algorithm	numpy.matmul	Matrix multiply
Strassen's Algorithm	O(n^2.807)	Strassen impl	Ruby Strassen
Matrix Transpose	Computing A^T	numpy.transpose	Matrix.transpose
Matrix Trace	tr(A) = Σaᵢᵢ	numpy.trace	Matrix trace
Matrix Powers	A^k efficiently	matrix_power	Matrix powers
Kronecker Product	A ⊗ B	numpy.kron	Custom Kronecker

II. Linear System Solution Algorithms

Direct Methods - Gaussian Elimination Family

Algorithm	Description	Python	Ruby
Basic Gaussian Elimination	Forward elim + back sub	Custom impl	Ruby GE
GE with Partial Pivoting	Row pivoting	scipy.linalg.solve	NMatrix
LU Decomposition	A = LU	scipy.linalg.lu	NMatrix LU
LU with Pivoting	PA = LU	lu_factor	Numo::Linalg

Direct Methods - Cholesky Family

Algorithm	Description	Python	Ruby
Cholesky Decomposition	A = LL^T (pos def)	scipy.linalg.cholesky	NMatrix Cholesky
LDL^T Decomposition	A = LDL^T	scipy.linalg.ldl	Ruby LDL
Modified Cholesky	For indefinite matrices	Custom impl	Advanced Cholesky

Iterative Methods - Basic

Algorithm	Description	Python	Ruby
Jacobi Method	Simple iterative solver	Jacobi impl	Ruby Jacobi
Gauss-Seidel Method	Sequential updates	GS solver	Iterative methods
SOR	Successive over-relaxation	SOR impl	Ruby SOR

Iterative Methods - Krylov Subspace

Algorithm	Description	Python	Ruby
Conjugate Gradient	For SPD systems	scipy.sparse.linalg.cg	Ruby CG
BiCG-STAB	Stabilized BiCG	bicgstab	Stabilized methods
GMRES	Generalized minimal residual	gmres	GMRES impl

III. Eigenvalue and Singular Value Algorithms

Eigenvalue Methods

Algorithm	Description	Python	Ruby
QR Algorithm	All eigenvalues	scipy.linalg.eig	NMatrix eig
Power Method	Dominant eigenvalue	Custom power	Ruby power
Inverse Power Method	Specific eigenvalue	Inverse power	Inverse iteration
Lanczos Method	Symmetric sparse	scipy.sparse.linalg.eigsh	Sparse methods
Arnoldi Method	Nonsymmetric sparse	scipy.sparse.linalg.eigs	Arnoldi impl

SVD Methods

Algorithm	Description	Python	Ruby
Full SVD	All singular values	scipy.linalg.svd	NMatrix SVD
Truncated SVD	Largest k values	scipy.sparse.linalg.svds	Truncated SVD
Randomized SVD	Approximate SVD	sklearn randomized_svd	Random methods

IV. Matrix Decomposition and Factorization Algorithms

QR Decomposition

Algorithm	Description	Python	Ruby
Householder QR	Using reflectors	scipy.linalg.qr	NMatrix QR
Givens QR	Using rotations	Givens impl	Ruby Givens
Modified Gram-Schmidt	Orthogonalization	MGS impl	Gram-Schmidt

Least Squares

Algorithm	Description	Python	Ruby
Normal Equations	A^T A x = A^T b	Custom impl	Normal eq
QR Least Squares	Using QR decomp	scipy.linalg.lstsq	NMatrix lstsq
Ridge Regression	L2 regularized	sklearn Ridge	Ruby ridge
LASSO	L1 regularized	sklearn Lasso	LASSO methods

V. Numerical Linear Algebra Infrastructure

BLAS (Basic Linear Algebra Subprograms)

Level	Operations	Python	Ruby
Level 1	Vector-vector (AXPY, DOT, NRM2)	NumPy basics	Numo::Linalg
Level 2	Matrix-vector (GEMV, GER)	scipy.linalg.blas	BLAS wrappers
Level 3	Matrix-matrix (GEMM, TRMM)	scipy.linalg.blas	Matrix ops

LAPACK Routines

Category	Routines	Python	Ruby
Linear Solvers	GESV, POSV	scipy.linalg.solve	LAPACK bindings
Least Squares	GELS, GELSY	scipy.linalg.lstsq	LS solvers
Eigenvalues	SYEV, GEEV	scipy.linalg.eig	Eigensolvers
SVD	GESVD, GESDD	scipy.linalg.svd	SVD routines

VI. Advanced and Specialized Algorithms

Matrix Functions

Function	Description	Python	Ruby
Matrix Exponential	e^A	scipy.linalg.expm	Matrix exp
Matrix Logarithm	log(A)	scipy.linalg.logm	Matrix log
Matrix Square Root	A^(1/2)	scipy.linalg.sqrtm	Matrix sqrt

Structured Matrices

Type	Description	Python	Ruby
Toeplitz	Constant diagonals	scipy.linalg.toeplitz	Toeplitz algs
Hankel	Constant anti-diagonals	scipy.linalg.hankel	Hankel methods
Circulant	FFT-based operations	scipy.linalg.circulant	Circulant algs
Vandermonde	Fast solvers	numpy.vander	Vandermonde

Randomized Linear Algebra

Algorithm	Description	Python	Ruby
Random Projections	JL embeddings	sklearn random_projection	Random proj
Sketching	Matrix sketching	Custom impl	Sketching methods

Additional Resources

Comprehensive Libraries

Python Ecosystem 🐍

NumPy - numpy.org - Fundamental array operations
SciPy - scipy.org - Advanced linear algebra and LAPACK
scikit-learn - scikit-learn.org - Machine learning algorithms
PyTorch - pytorch.org - Tensor computations with GPU
JAX - github.com/google/jax - Composable transformations

Ruby Ecosystem 💎

NMatrix - github.com/SciRuby/nmatrix - Dense/sparse matrices
Numo::Linalg - github.com/ruby-numo/numo-linalg - LAPACK/BLAS
Ruby Matrix - ruby-doc.org - Standard library
Numo::NArray - github.com/ruby-numo/numo-narray - N-dimensional arrays

Educational Resources 📚

Python

Linear Algebra Implementations - Clean algorithm implementations
Scientific Computing - Educational examples
Engineering Computations - Applied linear algebra
Matrix Computations - Comprehensive examples

Ruby

Linear Algebra Ruby - Pure Ruby implementations
RMatrix - Matrix operations
SciRuby Organization - Scientific computing ecosystem

Textbook References 📖

"Matrix Computations" by Gene H. Golub and Charles F. Van Loan
"Numerical Linear Algebra" by Lloyd N. Trefethen and David Bau III
"Applied Numerical Linear Algebra" by James W. Demmel
"Iterative Methods for Sparse Linear Systems" by Yousef Saad

Performance Libraries 🏭

Intel MKL - Optimized BLAS/LAPACK
OpenBLAS - Open source BLAS
ATLAS - Automatically Tuned Linear Algebra Software
cuBLAS - GPU-accelerated BLAS (NVIDIA)

How to Use This Document

For Learners

Start with Section I for basic operations
Progress to Section II for solving linear systems
Study Section III for eigenvalue problems
Explore advanced topics in Sections IV-VI

For Practitioners

Use the table format to quickly find implementations
Compare Python and Ruby approaches
Reference production libraries for actual work
Use educational links for understanding algorithms

For Researchers

Check textbook references for theoretical foundations
Explore specialized algorithms in Section VI
Review performance-oriented implementations
Consider contributing to open-source projects

License: This taxonomy is provided for educational purposes. Individual implementations are subject to their respective licenses.

Last Updated: December 2024

Contributors Welcome: Submit issues or pull requests to improve this taxonomy.