Collaborative Research: Polynomial filtering for nonsymmetric matrices

Nonsymmetric matrices arise in a wide range of problems in physical modeling and data science, including robotics, population dynamics, biotechnology, and artificial intelligence. This research will advance both the theoretical foundations and computational tools for efficiently solving a wide range of problems in this class. Algorithms for nonsymmetric matrices can demonstrate oscillatory behavior, which can cause practical and theoretical issues. In contrast, algorithms for symmetric matrices are characteristically nonoscillatory, and are generally well understood. The results of this work will address both theoretical and applied questions about algorithm design for nonsymmetric systems. The investigators will develop practical algorithms that accelerate existing computational pipelines with theoretical guarantees, improving technologies for physical modeling and data science. Results will be disseminated on publicly available platforms, and participating graduate students will receive training in computational methods and professional development. In many cases, complex eigenvalues arise due to intrinsic oscillatory modes that are fundamental to a given problem. Iterative linear algebra methods for such matrices generally lack convergence rate guarantees and may exhibit unexpected behavior in practice, presenting both theoretical and practical challenges. The goals of this work are to advance both the computational and theoretical foundations of iterative linear algebra methods by the development and analysis of new polynomial filtering methods that provably damp oscillatory eigenmodes. The objectives of this work include: (1) developing new polynomial constructions that enable novel preconditioning methods for Krylov subspace methods; and (2) using these polynomials to compress power series expansions, yielding provably fast algorithms for various linear algebra tasks, including iterative solvers for linear systems. This work has the potential to significantly advance the theory and application of iterative linear algebra methods for nonsymmetric matrices, leading to the development of both new algorithms and new theoretical understanding. 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.