Grant: Discovery Grants Program - Individual
University of Waterloo
$60,300.00
High Performance Graph Algorithms and Data Structures
FY 2022-23
Summary
Computation on large scale data is closely connected with tools such as linear system solvers, convex optimization, and systems for storing dynamically changing networks. These tools are integrated in many high-level programming languages such as MATLAB, Python, and Julia, which are in turn widely used in machine learning, statistics, and scientific computing. The long term goal of this research program is to develop a new generation of algorithmic primitives suitable for inputs several order of magnitudes larger than what we currently process. Specifically, we hope to develop highly efficient and theoretically well-founded algorithms for processing graphs and sparse matrices in both static and dynamic settings. It builds upon recent breakthroughs in algorithms for fundamental graph problems, namely almost nearly-linear time solvers for graph structured linear systems, faster algorithms for network flows, and dynamic maintenance of higher connectivity values. The shorter term (5 year) objectives are: * Investigate and classify structured sparse linear systems, especially ones related to graphs, with the goal of refining and improving numerical primitives for manipulating them. * Develop almost linear time algorithms for solving wide ranges of graph optimization problems to high accuracy. * Better understand data structures for maintaining solutions of optimization problems on dynamically changing graphs. The proposed work revolves around two of the most widely used numerical primitives: iteration and elimination. Generalizing them to wide classes of computational problems will lead to a host of new algorithmic primitives suitable for the large-scale graph and sparse matrices. Such primitives are the silent workhorse of much of large-scale computation today, including the search engines that power the modern internet. Improvements on them have led to, and will continue to lead to, accelerated drug design, better social network analytics, more accurate recommendation of products to users, and more. This research program includes the supervision of both undergraduate and graduate students, the development of courses that connect numerical and combinatorial algorithms, as well as the organization of algorithmic problem solving outreach activities. Students involved will gain knowledge in the latest development of algorithms, develop independent research skills, and gain supervision/organization experiences through involvements in outreach activities. Such skills are highly sought after in both industry and academia: for example, the social media company Facebook has plans of hiring 35000 employees in its Bay Area facility, the web-based delivery company Amazon expanded by about 50% over the past year, the Computer Research Association reported that the size of CS programs tripled on average between 2006 and 2017, and major research universities hired over 70 faculties in theoretical computer science during the 2021-2022 cycle.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-03207
Name nom
Peng, Yang (Richard)
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2022
Award amount
60300
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
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1
Partie
1
Nb partie
5
Application title
High Performance Graph Algorithms and Data Structures
Application summary
Computation on large scale data is closely connected with tools such as linear system solvers, convex optimization, and systems for storing dynamically changing networks. These tools are integrated in many high-level programming languages such as MATLAB, Python, and Julia, which are in turn widely used in machine learning, statistics, and scientific computing. The long term goal of this research program is to develop a new generation of algorithmic primitives suitable for inputs several order of magnitudes larger than what we currently process. Specifically, we hope to develop highly efficient and theoretically well-founded algorithms for processing graphs and sparse matrices in both static and dynamic settings. It builds upon recent breakthroughs in algorithms for fundamental graph problems, namely almost nearly-linear time solvers for graph structured linear systems, faster algorithms for network flows, and dynamic maintenance of higher connectivity values. The shorter term (5 year) objectives are: * Investigate and classify structured sparse linear systems, especially ones related to graphs, with the goal of refining and improving numerical primitives for manipulating them. * Develop almost linear time algorithms for solving wide ranges of graph optimization problems to high accuracy. * Better understand data structures for maintaining solutions of optimization problems on dynamically changing graphs. The proposed work revolves around two of the most widely used numerical primitives: iteration and elimination. Generalizing them to wide classes of computational problems will lead to a host of new algorithmic primitives suitable for the large-scale graph and sparse matrices. Such primitives are the silent workhorse of much of large-scale computation today, including the search engines that power the modern internet. Improvements on them have led to, and will continue to lead to, accelerated drug design, better social network analytics, more accurate recommendation of products to users, and more. This research program includes the supervision of both undergraduate and graduate students, the development of courses that connect numerical and combinatorial algorithms, as well as the organization of algorithmic problem solving outreach activities. Students involved will gain knowledge in the latest development of algorithms, develop independent research skills, and gain supervision/organization experiences through involvements in outreach activities. Such skills are highly sought after in both industry and academia: for example, the social media company Facebook has plans of hiring 35000 employees in its Bay Area facility, the web-based delivery company Amazon expanded by about 50% over the past year, the Computer Research Association reported that the size of CS programs tripled on average between 2006 and 2017, and major research universities hired over 70 faculties in theoretical computer science during the 2021-2022 cycle.