8. Fast algorithms for highly oscillatory problems (Stanford)
Research thrusts: Fast & reliable solution of multiphysics/multiscale problems
Research sub-thrusts: Fast solvers; Accurate, robust discretizations
Many problems of particular interest to DOE are highly oscillatory, including problems from sonar and radar imaging, computational chemistry, and condensed matter physics. In the past twenty years, modern computational methods have been developed and have become essential tools for understanding these phenomena. However, accurate and efficient solution of these oscillatory problems remain challenging due to the vast problem size and the indefinite nature of the linear operator. The Stanford group has made significant progress in developing novel and practical algorithms for these problems.
We have developed fast solvers and preconditioners for time harmonic high frequency wave problems
 |
 |
in acoustics and electromagnetics. Among them, the sweeping preconditioner and the sparsifying preconditioner have become the most effective methods developed to date for the differential and integral formulations, respectively. These results have appeared in top-tier scientific journals [72, 74, 75, 81, 82, 83, 86, 139, 140, 142, 143, 144, 145]. The wave fields in Fig. 11 are obtained with the sparsifying preconditioner in fewer than 10 iterations.
We have also developed efficient algorithms for electronic structure calculation, mostly under the framework of density functional theory and tensor networks. The common theme behind this work is identifying the unique geometry and algebraic structures (such as low-rankness, sparsity, multiscale renormalization) and utilizing these structures for developing highly effective and accurate algorithms. The results have appeared or been submitted to top-tier applied mathematics journals [39, 40, 41, 79, 84, 85, 141]. Fig. 12 demonstrates the compressed Kohn-Sham orbitals (or Wannier functions) by directly using selected columns of the density matrix (SCDM) developed by our team.
 |
 |
Finally, we have also developed disruptive technologies for fast solution for elliptic-type problems in both differential and integral formulations [58, 59, 73, 97, 98]. By combining the key ideas of multigrid, wavelet, and renormalization together, these methods employ efficient on-the-fly basis changes in order to represent linear differential and integral operators from PDE and data analysis in a data-sparse fashion. The resulting factorization supports matrix functions, linear system solves, and determinant analysis in an almost trivial way.