CAREER: Fine-Grained Complexity and Algorithms for Structured Linear Equations and Linear Programs

点击翻译按钮获取中文摘要

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.