Numerical linear algebra List of numerical analysis topics

1 numerical linear algebra

1.1 basic concepts
1.2 solving systems of linear equations
1.3 eigenvalue algorithms
1.4 other concepts , algorithms

numerical linear algebra

numerical linear algebra — study of numerical algorithms linear algebra problems

basic concepts

types of matrices appearing in numerical analysis:

sparse matrix

band matrix
bidiagonal matrix
tridiagonal matrix
pentadiagonal matrix
skyline matrix


circulant matrix
triangular matrix
diagonally dominant matrix
block matrix — matrix composed of smaller matrices
stieltjes matrix — symmetric positive definite non-positive off-diagonal entries
hilbert matrix — example of matrix extremely ill-conditioned (and difficult handle)
wilkinson matrix — example of symmetric tridiagonal matrix pairs of nearly, not exactly, equal eigenvalues
convergent matrix – square matrix successive powers approach 0 matrix


algorithms matrix multiplication:

strassen algorithm
coppersmith–winograd algorithm
cannon s algorithm — distributed algorithm, suitable processors laid out in 2d grid
freivalds algorithm — randomized algorithm checking result of multiplication


matrix decompositions:

lu decomposition — lower triangular times upper triangular
qr decomposition — orthogonal matrix times triangular matrix

rrqr factorization — rank-revealing qr factorization, can used compute rank of matrix


polar decomposition — unitary matrix times positive-semidefinite hermitian matrix
decompositions similarity:

eigendecomposition — decomposition in terms of eigenvectors , eigenvalues
jordan normal form — bidiagonal matrix of form; generalizes eigendecomposition

weyr canonical form — permutation of jordan normal form


jordan–chevalley decomposition — sum of commuting nilpotent matrix , diagonalizable matrix
schur decomposition — similarity transform bringing matrix triangular matrix


singular value decomposition — unitary matrix times diagonal matrix times unitary matrix


matrix splitting – expressing given matrix sum or difference of matrices

solving systems of linear equations

gaussian elimination

row echelon form — matrix in entries below nonzero entry zero
bareiss algorithm — variant ensures entries remain integers if initial matrix has integer entries
tridiagonal matrix algorithm — simplified form of gaussian elimination tridiagonal matrices


lu decomposition — write matrix product of upper- , lower-triangular matrix

crout matrix decomposition
lu reduction — special parallelized version of lu decomposition algorithm


block lu decomposition
cholesky decomposition — solving system positive definite matrix

minimum degree algorithm
symbolic cholesky decomposition


iterative refinement — procedure turn inaccurate solution in more accurate one
direct methods sparse matrices:

frontal solver — used in finite element methods
nested dissection — symmetric matrices, based on graph partitioning


levinson recursion — toeplitz matrices
spike algorithm — hybrid parallel solver narrow-banded matrices
cyclic reduction — eliminate or odd rows or columns, repeat
iterative methods:

jacobi method
gauss–seidel method

successive over-relaxation (sor) — technique accelerate gauss–seidel method

symmetric successive overrelaxation (ssor) — variant of sor symmetric matrices


backfitting algorithm — iterative procedure used fit generalized additive model, equivalent gauss–seidel


modified richardson iteration
conjugate gradient method (cg) — assumes matrix positive definite

derivation of conjugate gradient method
nonlinear conjugate gradient method — generalization nonlinear optimization problems


biconjugate gradient method (bicg)

biconjugate gradient stabilized method (bicgstab) — variant of bicg better convergence


conjugate residual method — similar cg assumed matrix symmetric
generalized minimal residual method (gmres) — based on arnoldi iteration
chebyshev iteration — avoids inner products needs bounds on spectrum
stone s method (sip – srongly implicit procedure) — uses incomplete lu decomposition
kaczmarz method
preconditioner

incomplete cholesky factorization — sparse approximation cholesky factorization
incomplete lu factorization — sparse approximation lu factorization


uzawa iteration — saddle node problems


underdetermined , overdetermined systems (systems have no or more 1 solution):

numerical computation of null space — find solutions of underdetermined system
moore–penrose pseudoinverse — finding solution smallest 2-norm (for underdetermined systems) or smallest residual
sparse approximation — finding sparsest solution (i.e., solution many zeros possible)



eigenvalue algorithms

eigenvalue algorithm — numerical algorithm locating eigenvalues of matrix

power iteration
inverse iteration
rayleigh quotient iteration
arnoldi iteration — based on krylov subspaces
lanczos algorithm — arnoldi, specialized positive-definite matrices

block lanczos algorithm — when matrix on finite field


qr algorithm
jacobi eigenvalue algorithm — select small submatrix can diagonalized exactly, , repeat

jacobi rotation — building block, givens rotation
jacobi method complex hermitian matrices


divide-and-conquer eigenvalue algorithm
folded spectrum method
lobpcg — locally optimal block preconditioned conjugate gradient method
eigenvalue perturbation — stability of eigenvalues under perturbations of matrix

other concepts , algorithms

orthogonalization algorithms:

gram–schmidt process
householder transformation

householder operator — analogue of householder transformation general inner product spaces


givens rotation


krylov subspace
block matrix pseudoinverse
bidiagonalization
cuthill–mckee algorithm — permutes rows/columns in sparse matrix yield narrow band matrix
in-place matrix transposition — computing transpose of matrix without using additional storage
pivot element — entry in matrix on algorithm concentrates
matrix-free methods — methods access matrix evaluating matrix-vector products