Support-Graph PreconditioningSystems of Linear Equations: Ax = bGraphs and Sparse Matrices [Parter, … ]Fill-reducing matrix permutationsConjugate gradient iterationConjugate gradient: ConvergencePreconditionersSupport Graph PreconditioningSpanning Tree Preconditioner [Vaidya]Slide 16Slide 17Support Graphs [after Gremban/Miller/Zagha]Splitting and Congestion/Dilation LemmasSupport-graph analysis of modified incomplete CholeskySupporting positive edges of BAnalysis of MIC: SummarySupport-graph analysis for better preconditioners?Hierarchical preconditioner (1D model problem)Hierarchical preconditioner continuedSlide 26Generalization to higher dimensions?Algebraic frameworkAlgebraic framework [Boman/Hendrickson]PowerPoint PresentationOpen problems IOpen problems IIComplexity of linear solversReferencesSupport-Graph Support-Graph PreconditioningPreconditioningJohn R. GilbertMIT and U. C. Santa Barbaracoauthors: Marshall Bern, Bruce Hendrickson, Nhat Nguyen, Sivan Toledoauthors of other work surveyed: Erik Boman, Doron Chen, Keith Gremban, Bruce Hendrickson, Gary Miller, Sivan Toledo, Pravin Vaidya, Marco ZaghaSystems of Linear Equations: Ax = bSystems of Linear Equations: Ax = b•A is large & sparse•say n = 105 to 108, # nonzeros = O(n)•Physical setting sometimes implies G(A) has separators•O(n1/2) in 2D, O(n2/3) in 3D•Here: A is symmetric and positive (semi)definite•Direct methods: A=LU•Iterative methods: y(k+1) = Ay(k)Graphs and Sparse MatricesGraphs and Sparse Matrices [Parter, … ]1013245678910132456789G(A)G+(A)[chordal]Symmetric Gaussian elimination:for j = 1 to n add edges between j’s higher-numbered neighborsFill: new nonzeros in factorElimination tree with nested dissectionFill-reducing matrix permutationsFill-reducing matrix permutations•Theory: approx optimal separators => approx optimal fill and flop count•Orderings: nested dissection, minimum degree, hybrids•Graph partitioning: spectral, geometric, multilevelVertex separator in graph of matrix0 50 100020406080100120nz = 844Matrix reordered by nested dissectionConjugate gradient iterationConjugate gradient iteration•One matrix-vector multiplication per iteration•Two vector dot products per iteration•Four n-vectors of working storagex0 = 0, r0 = b, p0 = r0for k = 1, 2, 3, . . .αk = (rTk-1rk-1) / (pTk-1Apk-1) step lengthxk = xk-1 + αk pk-1 approx solution rk = rk-1 – αk Apk-1 residualβk = (rTk rk) / (rTk-1rk-1) improvementpk = rk + βk pk-1 search directionConjugate gradient: ConvergenceConjugate gradient: Convergence•In exact arithmetic, CG converges in n steps (completely unrealistic!!)•Accuracy after k steps of CG is related to:•consider polynomials of degree k that are equal to 1 at 0.•how small can such a polynomial be at all the eigenvalues of A?•Thus, eigenvalues close together are good.•Condition number: κ(A) = ||A||2 ||A-1||2 = λmax(A) / λmin(A)•Residual is reduced by a constant factor by O(κ1/2(A)) iterations of CG.PreconditionersPreconditioners•Suppose you had a matrix B such that:(1) condition number κ(B-1A) is small(2) By = z is easy to solve•Then you could solve (B-1A)x = B-1b instead of Ax = b(actually (B-1/2AB-1/2) B1/2 x = B-1/2 b, but never mind)•B = A is great for (1), not for (2)•B = I is great for (2), not for (1)Support Graph PreconditioningSupport Graph Preconditioning+: New analytic tools, some new preconditioners+: Can use existing direct-methods software-: Current theory and techniques limited•Define a preconditioner B for matrix A•Explicitly compute the factorization B = LU•Choose nonzero structure of B to make factoring cheap (using combinatorial tools from direct methods)•Prove bounds on condition number using both algebraic and combinatorial toolsSpanning Tree Preconditioner Spanning Tree Preconditioner [Vaidya] •A is symmetric positive definite with negative off-diagonal nzs•B is a maximum-weight spanning tree for A (with diagonal modified to preserve row sums)•factor B in O(n) space and O(n) time•applying the preconditioner costs O(n) time per iterationG(A)G(B)Spanning Tree Preconditioner Spanning Tree Preconditioner [Vaidya] •support each edge of A by a path in B•dilation(A edge) = length of supporting path in B •congestion(B edge) = # of supported A edges•p = max congestion, q = max dilation•condition number κ(B-1A) bounded by p·q (at most O(n2))G(A)G(B)Spanning Tree Preconditioner Spanning Tree Preconditioner [Vaidya] •can improve congestion and dilation by adding a few strategically chosen edges to B•cost of factor+solve is O(n1.75), or O(n1.2) if A is planar•in experiments by Chen & Toledo, often better than drop-tolerance MIC for 2D problems, but not for 3D.G(A)G(B)Support Graphs Support Graphs [after Gremban/Miller/Zagha] Intuition from resistive networks: How much must you amplify B to provide the conductivity of A?•The support of B for A is σ(A, B) = min{τ : xT(tB – A)x  0 for all x, all t  τ}•In the SPD case, σ(A, B) = max{λ : Ax = λBx} = λmax(A, B) •Theorem:If A, B are SPD then κ(B-1A) = σ(A, B) · σ(B, A)Splitting and Congestion/Dilation LemmasSplitting and Congestion/Dilation Lemmas•Split A = A1+ A2 + ··· + Ak and B = B1+ B2 + ··· + Bk•Ai and Bi are positive semidefinite•Typically they correspond to pieces of the graphs of A and B (edge, path, small subgraph)•Lemma: σ(A, B)  maxi {σ(Ai , Bi)}•Lemma: σ(edge, path)  (worst weight ratio) · (path length)•In the MST case: •Ai is an edge and Bi is a path, to give σ(A, B)  p·q•Bi is an edge and Ai is the same edge, to give σ(B, A)  1Support-graph analysis of modified incomplete CholeskySupport-graph analysis of modified incomplete Cholesky•B has positive (dotted) edges that cancel fill•B has same row sums as AStrategy: Use the negative edges of B to support both the negative edges of A and the positive edges of B.-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1-1 -1-1-1-1 -1-1-1-1 -1-1AA = 2D model Poisson problem.5 .5 .5.5 .5 .5.5 .5 .5-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1-1 -1-1-1-1 -1-1-1-1 -1-1BB = MIC preconditioner for ASupporting positive edges of BSupporting positive edges of B•Every dotted (positive) edge in B is supported by two paths in B•Each solid edge of B supports one or two dotted edges•Tune fractions to