Efficient solutions of hierarchical systems of linear equations (Q1089723)

Several methods have been developed in the past for the efficient solution of sparse systems of linear equations with Gaussian elimination. The generalized nested dissection method finds an ordering of the rows and columns of the coefficient matrix that produces small fill-in. The substructure method exploits the hierarchical structure imposed on the coefficient matrix by nested dissection to circumvent the necessity for using general sparse matrix algorithms. This is accomplished by decomposing the matrix into submatrices solves them and reassembles the solution. We take the approach of the substructure method one step further: In many engineering applications such as finite element problems and circuit analysis problems many of the submatrices are identical. We exploit this fact to drastically reduce the space requirements for solving systems of linear equations that are defined succinctly using hierarchical definitions. Furthermore, if only a few components of the solution vector are asked for, we can by the same token achieve drastic savings of computing time. We get our results by extending a method for hierarchical graph processing to matrix computation. Our approach generalizes special solutions that have been published before in the finite element literature.