matrix structure and algorithm complexity solving linear ...

Convex Optimization Boyd & Vandenberghe9. Numerical linear algebra background matrix structure and algorithm complexity solving linear equations with factored matrices LU, Cholesky, LDLT factorization block elimination and the matrix inversion lemma solving underdetermined equations9 1 matrix 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) 2 NifAis 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 ...

Loading..

Tags:

  Matrix, Complexity, Factored

Information

Related search queries