Sparsity Preserving Algorithms for Rank Structured Systems

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

This project focuses on developing reliable and efficient computational methods for solving equations obtained from discretization of elliptic partial differential equations that arise in engineering and science. The methods are expected to be of direct use in the fast solution of various problems in electrostatics and materials engineering and also to have utility in accelerating computations associated with numerical methods for time dependent simulations. The project will extend a class of highly stable orthogonal methods based on sparse banded representations to equations with more complicated structures than have been considered before in the context of this class of algorithms. The stability and efficiency of the methods will be analyzed and an efficient software implementation of all the methods will be developed and released. The project involves the development of fast direct algorithms for elliptic partial differential equations. The methods are based on Givens-weight techniques that exploit rank structure in order to limit fill-in when computing a QR or LQ factorization. There are four main components to the project: The extension of orthogonal Givens-weight algorithms to strongly admissible rank structures, the development of efficient block operations acting on blocks that are obtained from discretization of particular subdomains, the analysis of the methods for numerical stability and complexity, and the development of an efficient software library implementing the algorithms. The overarching goal is to bridge a gap between the more flexible classes of methods that have uncertain numerical stability and the highly stable orthogonal methods that are applicable only to problems with a restricted weakly admissible rank structure. The techniques used are expected to lead to algorithms with linear or near-linear complexity, good practical efficiency, and provable backward stability. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.