The proposed research is concerned with innovative and systematic structured matrix computations. Large-scale matrices arise frequently in mathematical computations and engineering simulations. By exploiting the inherent structures, one can often develop new fast and reliable matrix methods. This work is especially interested in rank structures and data-sparse matrices, as well as innovative ideas of using them in the solutions of practical numerical problems (especially high dimensional discretized problems). The PI proposes to enhance both the flexibility and the applicability of structured methods. Systematic analysis for the structures and the methods will be included. The following aspects will be studied: (1) theoretical foundations of rank properties and new nested hierarchical structures; (2) new perspectives for exploring matrix structures, such as matrix-free structured sparse factorization, factorization update, and nested localization and sparsification; (3) efficient rank structured matrix algorithms, their analysis, and their use in fast solutions of large linear systems, least squares problems, eigenvalue problems, discretized PDEs, and numerous engineering applications.
Matrix computations lie at the heart of most scientific computation tasks. This research will systematically extend classical dense and sparse matrix computations to data-sparse ones, and will introduce new structured matrix theories and techniques into scientific and engineering computations. The project will result in practical ways to reveal and use structures, which will further yield fast and reliable algorithms such as stable direct three dimensional PDE solvers with nearly linear complexity. Understanding the structures will also provide new perspectives to classical challenges in numerical solutions, such as large fill-in, ill conditioning, lack of explicit matrices, and repeated solutions with highly varying parameters. The proposed algorithms can be used (say, as kernel solvers) in many complex numerical problems such as PDE solution, seismic imaging, signal processing, nanostructure modeling, and VLSI circuit simulation. The work will provide a multidisciplinary opportunity for researchers in different areas to participate. The project will result in freely available open source packages for practical applications, as well as courses ad tutorial and test materials for educational outreach programs that can stimulate the interest and achievement of students from diverse backgrounds.
