Randomized methods for accelerating linear solvers and matrix factorization algorithms
Abstract
The project supports the development of new algorithms for performing commonly used matrix computations that will greatly accelerate computational simulations and data analysis. Specific objectives include:(1) Faster algorithms for computing full and partial matrix factorizations such as, e.g., the singular value decomposition, and the column pivoted QR factorization.(2) Faster algorithms for solving linear systems Ax = b involving a broad class of densecoefficient matrices.(3) New algorithms for computing data-sparse representations of so called ???rank structured??? matrices (H-matrices, HSS matrices, etc.). Such matrices provide powerful tools for computational simulations, and for analyzing certain stochastic processes.(4) Improved direct (as opposed to iterative) solvers for linear elliptic PDEs that model problems such as acoustic and electro-magnetic scattering, composite materials, integrated circuits, and many more.The objectives will be achieved by exploiting recently developed techniques that use randomized projections to reduce the effective dimensionality of intermediate problems, while still maintaining high accuracy in the final answer. The new algorithms will be much more communication efficient than existing techniques and will in consequence execute faster on single CPU machines, and much faster on more severely communication constrained environments such as GPUs, out-of-core computations, and distributed memory machines. By accelerating key matrix computations, the proposed work would greatly enhance the power of data discovery with applications in speech and image recognition, video compression, analysis of large graphs and networks, machine learning, and many other applications of high relevance to the Navy. In scientific computing, the work supported will directly facilitate the development of a new generation of direct solvers for elliptic PDEs with excellent scaling properties. Applications of particular relevance to the US Navy include: electromagnetics (antenna design, minimizing radar cross sections, etc.), acoustics (sonar, minimizing noise, etc.), design of new micro-structured materials by performing static and dynamic simulations of the elasticity equations (bandgap materials, etc.), imaging (forwards and backwards scattering, etc), and many more.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 10, 2018
- Source ID
- N000141812354
Entities
People
- Per-Gunnar Johan Martinsson
Organizations
- Office of Naval Research
- United States Navy
- University of Texas at Austin