Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$66,000.00

Design of Fast Algorithms using Continuous Methods

EF 2023-24

Résumé
In this proposal, we aim to develop fast algorithms for several classic graph problems and numerical linear algebra problems using methods from continuous optimization and random matrix analysis. The use of tools from continuous optimization has been a major success story in the design of fast algorithms over the past few years. Combining tools such as near-linear time solvers for linear systems in Laplacian matrices from the seminal work of Spielman and Teng with methods from optimization such as gradient descent and interior point methods, has led to the development of the current fastest algorithms for classic combinatorial problems such as maximum flow, graph partitioning, bipartite matching, sampling random spanning trees etc.Over the past year, my co-authors and I have built on tools from random matrix theory for better analyzing randomized processes on graphs, resulting in an algorithmic tool we refer to as randomized elimination [Kyng et al 16, Kyng-Sachdeva '16]. This has already led to a number of advances, including the simplest Laplacian solver [Kyng-Sachdeva '16], nearly-linear time solver for linear systems in block diagonally dominant (bDD) matrices [Kyng et al '16] (these systems arise when analyzing cryo-electron microscopy data), faster algorithms for sampling random spanning trees in graphs [Durfee et al '17a], and approximating determinants of Laplacians [Durfee et al '17b].The key objective of this proposal is to develop these programs further and seek to design faster and improved algorithms for several fundamental problems. The first project under this proposal will be to develop randomized elimination based constructions for special trees. Specifically, we seek fast algorithms for low-stretch spanning trees, which are a fundamental component of several fast Laplacian solvers; and to incorporate random walk based ideas to design nearly-linear time algorithms for sampling random spanning trees.The second project under this proposal will be to develop faster and simpler algorithms for several fundamental flow problems on graphs, including maximum-flow, bipartite matching, and multi-commodity flow. These are classic problems in theoretical computer science, where decades-old running time barriers have been broken with the help of continuous methods.The third project under this proposal will be to build solvers for more classes of linear systems such as those arising from analyzing truss structures and RLC circuits. A particularly ambitious goal here is to design faster algorithms for solving systems of linear equations in all positive-semidefinite matrices, which would have immediate applications for basically all problems in numerical linear algebra.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2018-06398
Name nom
Sachdeva, Sushant
Department département
Department of Mathematical and Computational Sciences
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2018
Award amount
66000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Mathematics of computing
Research subject en
Technologie de l'information
Research subject fr
Mathématiques de l'informatique
Application title
Design of Fast Algorithms using Continuous Methods
Keyword
Algorithms; Continuous Optimization; Fast graph algorithms; Graph Laplacians; Linear systems; Numerical Linear Algebra; Random Matrix Analysis
Application summary
In this proposal, we aim to develop fast algorithms for several classic graph problems and numerical linear algebra problems using methods from continuous optimization and random matrix analysis. The use of tools from continuous optimization has been a major success story in the design of fast algorithms over the past few years. Combining tools such as near-linear time solvers for linear systems in Laplacian matrices from the seminal work of Spielman and Teng with methods from optimization such as gradient descent and interior point methods, has led to the development of the current fastest algorithms for classic combinatorial problems such as maximum flow, graph partitioning, bipartite matching, sampling random spanning trees etc.Over the past year, my co-authors and I have built on tools from random matrix theory for better analyzing randomized processes on graphs, resulting in an algorithmic tool we refer to as randomized elimination [Kyng et al 16, Kyng-Sachdeva '16]. This has already led to a number of advances, including the simplest Laplacian solver [Kyng-Sachdeva '16], nearly-linear time solver for linear systems in block diagonally dominant (bDD) matrices [Kyng et al '16] (these systems arise when analyzing cryo-electron microscopy data), faster algorithms for sampling random spanning trees in graphs [Durfee et al '17a], and approximating determinants of Laplacians [Durfee et al '17b].The key objective of this proposal is to develop these programs further and seek to design faster and improved algorithms for several fundamental problems. The first project under this proposal will be to develop randomized elimination based constructions for special trees. Specifically, we seek fast algorithms for low-stretch spanning trees, which are a fundamental component of several fast Laplacian solvers; and to incorporate random walk based ideas to design nearly-linear time algorithms for sampling random spanning trees.The second project under this proposal will be to develop faster and simpler algorithms for several fundamental flow problems on graphs, including maximum-flow, bipartite matching, and multi-commodity flow. These are classic problems in theoretical computer science, where decades-old running time barriers have been broken with the help of continuous methods.The third project under this proposal will be to build solvers for more classes of linear systems such as those arising from analyzing truss structures and RLC circuits. A particularly ambitious goal here is to design faster algorithms for solving systems of linear equations in all positive-semidefinite matrices, which would have immediate applications for basically all problems in numerical linear algebra.