matrix structure and algorithm complexity solving linear ...

← Back to document page

Convex Optimization Boyd & Vandenberghe9. Numerical linear algebra background matrix structure and algorithm complexity solving linear equations with factored matrices LU, Cholesky, LDLTfactorization block elimination and the matrix inversion lemma solving underdetermined equations9 1Matrix structure and algorithm complexitycost (execution time) of solvingAx=bwithA Rn n for general methods, grows asn3 less ifAis structured (banded, sparse, Toeplitz, . . . )flop counts flop (floating-point operation): one addition, subtraction,multiplication, or division of two floating-point numbers to estimate complexity of an algorithm : express number of flops as a(polynomial) function of the problem dimensions, and simplify bykeeping only the leading terms not an accurate predictor of computation time on modern computers useful as a rough estimate of complexityNumerical linear algebra background9 2vector-vector operations(x,y Rn) inner productxTy:2n 1flops (or2nifnis large) sumx+y, scalar multiplication x:nflopsmatrix-vector producty=AxwithA Rm n m(2n 1)flops (or2mnifnlarge) 2NifAis sparse withNnonzero elements 2p(n+m)ifAis given asA=U VT,U Rm p,V Rn pmatrix- matrix productC=ABwithA Rm n,B Rn p mp(2n 1)flops (or)

every nonsingular symmetric matrix A can be factored as A =PLDLTPT with P a permutation matrix, L lower triangular, D block diagonal with 1×1or 2×2diagonal blocks cost: (1/3)n3 • cost of solving symmetric sets of linear equations by LDLT factorization: (1/3)n3+2n2 ≈ (1/3)n3 for large n • for sparse A, can choose P to yield sparse L ...

  Matrix, Complexity, Factored