Fast randomized algorithms for global operators

Computational simulation is essential for designing electromagnetic devices, predicting radar and sonar signatures, improving medical imaging, modeling advanced materials and larger molecular systems, and testing physical systems before they are built. These applications often require solving mathematical models that are far too large for direct calculation using standard methods, especially in realistic three-dimensional geometries. A major obstacle is that the computer representation of the underlying physical system can become an enormous array of numbers (known as a "matrix"), so large that it is impractical to store or manipulate. This project develops new mathematical and computational tools that use randomization as an algorithmic engine: instead of exhaustively examining all interactions in a simulated physical system, the methods use carefully designed random probes to discover hidden structure and build compact representations. The resulting algorithms are expected to make large-scale simulations faster, more accurate, and less costly in memory, time, and energy. Potential benefits include improved tools for electromagnetic device design, radar and sonar modeling, medical imaging, nondestructive testing, materials modeling, molecular simulation, and simulations that combine several physical models or numerical methods. By strengthening a core capability of scientific computing, the project promotes the progress of science and supports national health, prosperity, and defense. The project also supports education by training a doctoral student in mathematical research, scientific computing, and high-performance computing, with connections to the Texas Advanced Computing Center. The work relates to national priorities in artificial intelligence by developing accuracy checks for AI-assisted scientific software and compact representations of physical systems that can support trustworthy machine-learning models and digital twins. The project develops fast randomized algorithms for global operators that arise in partial differential equations, wave propagation, inverse problems, sparse matrix computations, and other large-scale models in scientific computing. The central goal is to build data sparse representations of operators that are too large to form explicitly, using only the ability to apply the operator rapidly to selected input data. The research draws on numerical linear algebra, random matrix theory, computational harmonic analysis, high-dimensional probability, and rank structured matrix methods. It combines randomized probing, adaptive compression, graph-coloring strategies, structured sampling, and randomized embeddings to identify and exploit hidden low-dimensional structure in dense operators. These tools are used to accelerate direct solvers for large sparse linear systems by compressing the dense intermediate operators that arise during factorization. The project also develops stable multiplicative and unitary factorizations for rank structured matrices, randomized methods for oscillatory wave problems, and a posteriori error estimators that certify the accuracy of individual computations. A further goal is to reorganize the algorithms to reduce data movement and improve performance on modern high-performance computing platforms, including graphics processing units. The expected contributions are new algorithms that scale nearly linearly with problem size in important settings, more reliable direct solvers for difficult three-dimensional simulations, and a stronger mathematical foundation for randomized methods applied to continuum operators and large-scale scientific computing. 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. NSF Award ID: 2608883 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Per-Gunnar Martinsson | Institution: University of Texas at Austin, AUSTIN, TX | Award Amount: $320,000 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2608883 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2608883.html