| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | January 20, 2023 |
| Latest Amendment Date: | April 10, 2025 |
| Award Number: | 2238682 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Karl Wimmer
kwimmer@nsf.gov (703)292-2095 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | February 1, 2023 |
| End Date: | January 31, 2028 (Estimated) |
| Total Intended Award Amount: | $499,330.00 |
| Total Awarded Amount to Date: | $253,344.00 |
| Funds Obligated to Date: |
FY 2025 = $143,881.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3 RUTGERS PLZ NEW BRUNSWICK NJ US 08901-8559 (848)932-0150 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
110 Freinghuysen Rd Piscataway NJ US 08854-8087 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01002526DB NSF RESEARCH & RELATED ACTIVIT 01002627DB NSF RESEARCH & RELATED ACTIVIT 01002728DB 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.070 |
ABSTRACT
Abstract:
Linear equations and linear programs are ubiquitous in computational mathematics, engineering, machine learning, and data science, and they are powerful primitives for developing various algorithmic paradigms. Unfortunately, the currently best-known algorithms for solving general linear equations and linear programs run in super-quadratic time, which can be prohibitively slow for modern large-scale datasets. In practice, however, many linear equations and programs exhibit additional structures that enable significantly faster solvers. This project aims (1) to identify and classify structures that can accelerate solving linear equations and linear programs and those that can not and (2) to understand how fast we can solve general linear equations and linear programs. Another major part of this project is to provide multi-disciplinary education and research training for graduate, undergraduate, and high school students and to broaden the participation of women and underrepresented students in STEM fields.
This project aims to study fine-grained complexity and algorithms for structured linear equations and structured linear programs and focuses on three major goals. The first goal is to establish ``equivalent`` classes for structured linear equations and linear programs so that if we can solve one problem fast, we can immediately solve all the problems in the same equivalence class equally fast. The second goal is to develop efficient solvers for structured linear equations and linear programs that arise commonly from practice. Examples include generalized Laplacians with additional geometric structures, dense instances such as kernel matrices, and random instances. Finally, the third goal is to better understand the time complexity of general linear equations and linear programs. For example, can we solve general linear equations and linear programs faster than matrix multiplication? What are the runtime lower bounds under the Strong Exponential Time Hypothesis?
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.
Please report errors in award information by writing to: awardsearch@nsf.gov.
