Abstract

Can linear systems be solvedfaster than matrix multiplication? While there has been remarkable progress forthe special cases of graph structured linear systems, in the general setting,the bit complexity of solving an n-by-n linear system Ax=b is n^\omega, where\omega<2.372864 is the matrix multiplication exponent. Improving on this hasbeen an open problem even for sparse linear systems with poly(n) conditionnumber.

We present an algorithm thatsolves linear systems in sparse matrices asymptotically faster than matrixmultiplication for any \omega>2. This speedup holds for any input matrix Awith o(n^{\omega-1}/\log(\kappa(A))) non-zeros, where \kappa(A) is thecondition number of A. For poly(n)-conditioned matrices with O(n) nonzeros, andthe current value of \omega, the bit complexity of our algorithm to solve towithin any 1/poly(n) error is O(n^{2.331645}).

Our algorithm can be viewed asan efficient randomized implementation of the block Krylov method via recursivelow displacement rank factorizations. It is inspired by the algorithm of[Eberly-Giesbrecht-Giorgi-Storjohann-Villard ISSAC `06 `07] for invertingmatrices over finite fields. In our analysis of numerical stability, we developmatrix anti-concentration techniques to bound the smallest eigenvalue and thesmallest gap in eigenvalues of semi-random matrices.

Joint work with SantoshVempala, manuscript at https://arxiv.org/abs/2007.10254.

Time

3月22日  10:00--11:00

Speaker

Richard Peng isan assistant professor in the School of Computer Science at the GeorgiaInstitute of Technology. His research interests are in the design, analysis,and implementation of efficient algorithms. These interests currently revolvearound problems induced by practice that arise at the intersection of discrete,numerical, and randomized algorithms, and his representative results includelinear systems solvers, max-flow/min-cut algorithms, and time/space efficientdata structures for matchings, resistances, and matrices.

Richardreceived his BMath from Waterloo, PhD from CMU, and was a postdoc at MIT.Awards he received include the NSF Career Award, the 2011 Microsoft ResearchPhD Fellowship, the 2013 CMU SCS Distinguished Dissertation Award, and the 2021SODA Best Paper Award. Richard is extensively involved with algorithmic problemsolving outreach activities, including the North America Programming Camp andthe DMOJ Online Judge.

Venue

ZoomID:  63688419969

密码：123456