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 (or2mnpifnlarge) less

Matrix structure and algorithm complexity cost (execution time) of solving Ax =b with A ∈ Rn×n • for general methods, grows as n3 • less if A is structured (banded, sparse, Toeplitz, . . . ) flop counts • flop (floating-point operation): one addition, subtraction, multiplication, or division of two floating-point numbers

  Matrix, Multiplication, Complexity