Augmented Matrix Solvers for Dynamic System of Equations

In this dissertation, the problem of updating in real time the solution to a linear system of equations when a sequence of small changes is made to the data is considered. This problem arises in many computational science and engineering applications, and we consider two of them. The first is surgical simulations, where a simulator used to train surgeons needs to provide haptic feedback by updating the system ten to hundred times per second. The second is contingency analysis in the power grids, when their operators need to simulate a large number of scenarios to predict what could happen when elements of the grid fail. We observe that the changes in both applications result in the matrix\u27s being modified by a low-rank update within a principal submatrix. In the surgical simulations, the dimension of the matrix changes while it is being updated, since the matrix arises from a finite element mesh that is being cut, and we have to remesh around the cut during the update. In the power grid problem, the size of the matrix remains unchanged. AMPS, our augmented matrix solver, updates the solution by means of an augmented matrix formulation, in which all changes made to the coefficient matrix are represented by adding rows and columns to the initial matrix. Our approach keeps the initial matrix as a submatrix of the new system of equations and the subsequent updates are accounted for by augmenting the system in blocked form. We characterize the situations when the matrix updates lead to nonsingular systems of equations when the initial matrix is nonsingular. The intactness of the initial matrix allows us to compute its factors only once, and then without refactoring the modified matrix, we solve the augmented system by means of the Schur complement. A number of approaches, including direct methods, which factor the Schur complement and iterative methods, which use Krylov space solvers, are then available to solve the system. To accelerate the computation, we utilize the precomputed factors of the initial matrix and the solutions to the original system of equations, exploit the sparsity of the matrices and vectors, and apply memoization and parallelization techniques. By analyzing the time complexity of our solver, we show that the running time of AMPS is O(mρ+: L:), where m is the dimension of the principal submatrix, ρ is the number of nonzeros in a subset of the columns of the Cholesky factor L that are selected by the nonzeros in the sparse right-hand-side vector, and :L: is the number of nonzeros in L. We also show that AMPS has an asymptotically lower time complexity relative to other existing methods. Experimental results establish the competitiveness of AMPS by demonstrating that it outperforms a state of the art direct solver by two orders of magnitude, and earlier methods that update the matrix factors by 5 to 27 times, in the contingency analysis of a 777K node power-flow system. The computed solutions have accuracy comparable to those computed by a direct solver. Real-time solutions can also be provided using AMPS in the surgical simulation with more than 10 updates per second for a brain model of 50K nodes, and more than 30 updates per second for an eye model of 18K nodes