Transcription of matrix structure and algorithm complexity solving linear ...
{{id}} {{{paragraph}}}
Example: marketing
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 (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
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: