Convex Optimization Boyd Vandenberghe 9 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 equations 9 1 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 to estimate complexity of an algorithm express number of flops as a polynomial function of the problem dimensions and simplify by keeping only the leading terms not an accurate predictor of computation time on modern computers useful as a rough estimate of complexity Numerical linear algebra background 9 2 vector vector operations x y Rn inner product xT y 2n 1 flops or 2n if n is large sum x y scalar multiplication x n flops matrix vector product y Ax with A Rm n m 2n 1 flops or 2mn if n large 2N if A is sparse with N nonzero elements 2p n m if A is given as A U V T U Rm p V Rn p matrix matrix product C AB with A Rm n B Rn p mp 2n 1 flops or 2mnp if n large less if A and or B are sparse 1 2 m m 1 2n 1 m2n if m p and C symmetric Numerical linear algebra background 9 3 Linear equations that are easy to solve diagonal matrices aij 0 if i 6 j n flops x A 1b b1 a11 bn ann lower triangular aij 0 if j i n2 flops x1 b1 a11 x2 b2 a21x1 a22 x3 b3 a31x1 a32x2 a33 xn bn an1x1 an2x2 an n 1xn 1 ann called forward substitution upper triangular aij 0 if j i n2 flops via backward substitution Numerical linear algebra background 9 4 orthogonal matrices A 1 AT 2n2 flops to compute x AT b for general A less with structure e g if A I 2uuT with kuk2 1 we can compute x AT b b 2 uT b u in 4n flops permutation matrices aij 1 j i 0 otherwise where 1 2 n is a permutation of 1 2 n interpretation Ax x 1 x n satisfies A 1 AT hence cost of solving Ax b is 0 flops example 0 1 0 A 0 0 1 1 0 0 Numerical linear algebra background A 1 0 0 1 AT 1 0 0 0 1 0 9 5 The factor solve method for solving Ax b factor A as a product of simple matrices usually 2 or 3 A A 1 A2 Ak Ai diagonal upper or lower triangular etc 1 1 A compute x A 1b A 1 2 A1 b by solving k easy equations k A1x1 b A2 x 2 x 1 Ak x xk 1 cost of factorization step usually dominates cost of solve step equations with multiple righthand sides Ax1 b1 Ax2 b2 Axm bm cost one factorization plus m solves Numerical linear algebra background 9 6 LU factorization every nonsingular matrix A can be factored as A P LU with P a permutation matrix L lower triangular U upper triangular cost 2 3 n3 flops Solving linear equations by LU factorization given a set of linear equations Ax b with A nonsingular 1 LU factorization Factor A as A P LU 2 3 n3 flops 2 Permutation Solve P z1 b 0 flops 3 Forward substitution Solve Lz2 z1 n2 flops 4 Backward substitution Solve U x z2 n2 flops cost 2 3 n3 2n2 2 3 n3 for large n Numerical linear algebra background 9 7 sparse LU factorization A P1LU P2 adding permutation matrix P2 offers possibility of sparser L U hence cheaper factor and solve steps P1 and P2 chosen heuristically to yield sparse L U choice of P1 and P2 depends on sparsity pattern and values of A cost is usually much less than 2 3 n3 exact value depends in a complicated way on n number of zeros in A sparsity pattern Numerical linear algebra background 9 8 Cholesky factorization every positive definite A can be factored as A LLT with L lower triangular cost 1 3 n3 flops Solving linear equations by Cholesky factorization given a set of linear equations Ax b with A Sn 1 Cholesky factorization Factor A as A LLT 1 3 n3 flops 2 Forward substitution Solve Lz1 b n2 flops 3 Backward substitution Solve LT x z1 n2 flops cost 1 3 n3 2n2 1 3 n3 for large n Numerical linear algebra background 9 9 sparse Cholesky factorization A P LLT P T adding permutation matrix P offers possibility of sparser L P chosen heuristically to yield sparse L choice of P only depends on sparsity pattern of A unlike sparse LU cost is usually much less than 1 3 n3 exact value depends in a complicated way on n number of zeros in A sparsity pattern Numerical linear algebra background 9 10 LDLT factorization every nonsingular symmetric matrix A can be factored as A P LDLT P T with P a permutation matrix L lower triangular D block diagonal with 1 1 or 2 2 diagonal 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 cost 1 3 n3 Numerical linear algebra background 9 11 Equations with structured sub blocks A11 A12 A21 A22 x1 x2 b1 b2 1 variables x1 Rn1 x2 Rn2 blocks Aij Rni nj if A11 is nonsingular can eliminate x1 x1 A 1 11 b1 A12 x2 to compute x2 solve 1 A x b A A A22 A21A 1 12 2 2 21 11 b1 11 Solving linear equations by block elimination given a nonsingular set of linear equations 1 with A11 nonsingular 1 1 Form A 1 11 A12 and A11 b1 1 2 Form S A22 A21A 1 11 A12 and b b2 A21 A11 b1 3 Determine x2 by solving Sx2 b 4 Determine x1 by solving A11x1 b1 A12x2 Numerical linear algebra background 9 12 dominant terms in flop count step 1 f n2s f is cost of factoring A11 s is cost of solve step step 2 2n22n1 cost dominated by product of A21 and A 1 11 A12 step 3 2 3 n32 total f n2s 2n22n1 2 3 n32 examples general A11 f 2 3 n31 s 2n21 no gain over standard method flops 2 3 n31 2n21n2 2n22n1 2 3 n32 2 3 n1 n2 3 block elimination is useful for structured A11 f n31 for example diagonal f 0 s n1 flops 2n22n1 2 3 n32 Numerical linear algebra background 9 13 Structured matrix plus low rank term A BC x b A Rn n B Rn p C Rp n assume A has structure Ax b easy to solve first write as A B C I x y b 0 …