| NSF Org: |
DMS Division Of Mathematical Sciences |
| Recipient: |
|
| Initial Amendment Date: | August 3, 2019 |
| Latest Amendment Date: | June 27, 2022 |
| Award Number: | 1945652 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Pedro Embid
DMS Division Of Mathematical Sciences MPS Directorate for Mathematical and Physical Sciences |
| Start Date: | July 1, 2019 |
| End Date: | June 30, 2023 (Estimated) |
| Total Intended Award Amount: | $432,352.00 |
| Total Awarded Amount to Date: | $432,352.00 |
| Funds Obligated to Date: |
FY 2019 = $146,758.00 FY 2020 = $103,946.00 FY 2021 = $64,947.00 FY 2022 = $68,464.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
4333 BROOKLYN AVE NE SEATTLE WA US 98195-1016 (206)543-4043 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
WA US 98195-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
OFFICE OF MULTIDISCIPLINARY AC, APPLIED MATHEMATICS, Division Co-Funding: CAREER |
| Primary Program Source: |
01001920DB NSF RESEARCH & RELATED ACTIVIT 01002021DB NSF RESEARCH & RELATED ACTIVIT 01002122DB NSF RESEARCH & RELATED ACTIVIT 01002223DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.049 |
ABSTRACT
Numerical algorithms are pervasive in our lives today. These algorithms are used, for example, to send data to mobile devices and to simulate fire and water in movies. Many of the most classical algorithms, and particularly those with applications in linear algebra, have been extremely useful for decades, if not centuries. Yet, some of these algorithms are poorly understood -- they can fail catastrophically, but rarely do. In other words, the worst-case behavior is poor, but the average-case behavior is good. This research will advance the understanding of this phenomenon by employing techniques from the ever-expanding field of random matrix theory (RMT). In turn, this research gives rise to new questions within RMT. A substantial feature of this project is the extensive educational component that integrates research and education. This integration is achieved via a three-pronged approach including a summer workshop on random matrices, high school engagement, and undergraduate/graduate student mentoring.
Two natural ways to employ RMT within numerical linear algebra also coincide with the two most common themes in numerical linear algebra: Algorithm analysis and algorithm development. For example, remarkably detailed estimates from RMT such as rigidity and edge universality have found concrete applications within numerical linear algebra giving average-case performance for the classical power method. Randomized algorithms have found great utility in the big-data age. This research will employ both of these themes with applications to data science, psychology and beyond. The synergy of the fields of RMT and numerical linear algebra provides a unique educational opportunity for graduate, undergraduate and high school students.
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Random matrix theory and numerical linear algebra have been tied since essentially the inception of the digital computer. This 5 year CAREER award has aided in the further exploration of connections between these two areas and the development of applications based on their synergy.
The research during the grant period culminated in the development of a new theory that gives a significant step forward in the understanding of widely-used numerical algorithms when applied in a randomized setting.
This understanding was the result of a number of technical advances:
-
The demonstration of a concentration of measure phenomenon in the conjugate gradient algorithm, which shows that deterministic behavior is possible in random contexts.
-
The development of a theory of universality which expands the scope and the applicability of the first observation.
-
The application of the theory to the famed spiked covariance matrix model from statistics.
-
The novel use of the so-called Fokas-Its-Kitaev Riemann-Hilbert problem to perform a perturbation analysis.
It is expected that the theory developed here will result in new, efficient, theory-based statistical tools.
Select additional outcomes are as follows:
-
In 1995, Parker showed that by randomizing a matrix with butterfly matrices, one can avoid the need for pivoting in Gaussian elimination and not affect the leading-order complexity of the algorithm. Pivoting is a necessary tool to solve general systems of linear equations, but can be expensive in the age of parallel computations. An analysis of the so-called growth factor associated with these matrices was performed by the PI and collaborator to help understand the stability of this algorithm and the propagation of rounding errors within it.
-
With collaborators, the PI presented a new unified analysis and understanding of stochastic Lanczos quadrature, unifying it with the so-called kernel polynomial method. This randomized algorithm allows one to access information within a matrix when that matrix is too large to store in the memory of a computer. The analysis gives a streamlined framework to use both algorithms simultaneously.
Last Modified: 08/22/2023
Modified by: Thomas D Trogdon
Please report errors in award information by writing to: awardsearch@nsf.gov.
