In this project, the investigator and his students design new efficient structured matrix techniques for large linear systems, including fast direct solvers and robust effective preconditioners. These techniques take advantage of certain hidden rank structures in linear systems arising from practical applications. Efficient multi-layer structures and flexible rank requirements are considered. The methods have nearly linear complexity for linear systems arising from the discretization of certain partial differential equations. They can also work as effective preconditioners. Robustness of preconditioning for positive definite problems is shown. The methods are useful for problems which have been considered difficult for classical direct or iterative solvers.
This project has broader impacts in many complex numerical problems and engineering simulations, such as differential equations, seismic imaging, climate, electromagnetic field simulation, signal processing, and integrated circuit simulation. The major computational work in these applications is often to solve large-scale linear systems, which can benefit from the efficient black-box solvers or preconditioners developed in this project. These methods help break some classical lower complexity bounds. Students are involved in all aspects of the project, and are trained in various mathematical and engineering areas. The investigator's team plan to build a freely available open source package for both practical applications and education. Minisymposia organized by the investigator, as well as conferences talks, seminars, and journal articles, are used to exchange ideas and to disseminate the results.
This research has designed a series of new fast and reliable structured matrix techniques for the solutions of large linear systems. They include efficient structured direct solvers for dense matrices such as Toeplitz problems and sparse matrices such as discretized PDEs, as well as robust and effective preconditioners. The direct solvers have complexity much lower than traditional optimal complexity bounds. Structures within diverse problem types are studied. New structured forms are designed, including the combination of multiple structure types and those based on randomization techniques. Comprehensive accuracy and stability analysis is conducted for the structured methods. The structures and methods are also shown to be relatively insensitive to some parameters, such as diagonal shifts. This is thus especially useful for situations with varying parameters, such as symmetric eigenvalue solutions via bisection with shifts. Flexible rank patterns are studied and proven for some problems. The research greatly extends the applicability and flexibility of fast structured solvers for general numerical computations. The research has been applied to many complex numerical computations and engineering simulations, such as PDE solutions, seismic modeling, imaging, and compressive sensing, where the core computations are often to solve large linear systems. The methods and analysis also help to improve the efficiency and reliability of other numerical methods, such as finite difference, finite element, and spectral solutions of differential equations. The project provides new strategies for some traditional difficult situations, such as problems with interfaces, repeated matrix factorizations with varying parameters, and solving Helmholtz equations in seismic imaging. Close collaborations with researchers from other areas (geophysics, engineering, etc.) and schools were established. Students were extensively involved in the project, and were trained in several mathematical and engineering areas. They were actively encouraged to participate in seminars, workshops, and conference. Two PhD students successfully graduated. One found an industry job and the other continues research as a postdoc in a university. A long list of papers were published. The findings were disseminated via numerous invited seminar/conference presentations. The solvers and the codes have also benefited the work of researchers in other disciplines and schools.
