# Stable Accurate Fast Robust Algorithms & Numerics

Publications Research Software Funding

The SAFRAN lab was born in April 2016 and resides at Room 203, SERC building at IISc.

## Publications

(16) Daniel Foreman-Mackey, Eric Agol, Ruth Angus, Sivaram Ambikasaran, "Fast and scalable Gaussian process modeling with applications to astronomical time series", Submitted to AAS journals. Preprint*
This relies on my earlier work "The Generalized Rybicki Press algorithm"

(15) Sivaram Ambikasaran, Krithika Narayanaswamy, "An accurate, fast, mathematically robust, universal, non-iterative algorithm for computing multi-component diffusion velocities", Proceedings of Combustion Institute. Preprint*/ Journal version

(14) Sivaram Ambikasaran, Carlos Borges, Lise-Marie Imbert-Gerard, Leslie Greengard, "Fast, adaptive, high order discretization of the Lippmann-Schwinger equation in two dimension", SIAM Journal of Scientific Computing. Preprint*/ Journal version

(13) Sivaram Ambikasaran, "Generalized Rybicki Press algorithm", Numerical Linear Algebra with Applications. Preprint*/ Journal version

(12) Sivaram Ambikasaran, Eric Darve, "The Inverse Fast Multipole Method" Preprint*

(11) Sivaram Ambikasaran, Michael O'Neil, Karan Raj Singh, "Fast symmetric factorization of hierarchical matrices with applications", Submitted Preprint*

(10) Jun Lai, Sivaram Ambikasaran, Leslie F. Greengard, "A fast direct solver for high frequency scattering from a large cavity in two dimensions", SIAM Journal of Scientific Computing. Preprint*/ Journal version
Here is a video of scattering from an engine shaped cavity. Fast direct solver is especially attractive in the present context, since it permits the computation of the scattered field for multiple incident angles in a negligible amount of time.

(9) Sivaram Ambikasaran, Daniel Foreman-Mackey, Leslie Greengard, David W. Hogg, Michael O'Neil, "Fast Direct Methods for Gaussian Processes and the Analysis of NASA Kepler Mission Data", Transactions on Pattern Analysis and Machine Intelligence. Preprint*/ Journal version

(8) Amirhossein Aminfar, Sivaram Ambikasaran, Eric Darve, "A fast block low-rank dense solver with applications to finite-element matrices", Journal of Computational Physics. Preprint*/ Journal version

(7) Judith Y Li, Sivaram Ambikasaran, Eric Darve, Peter K Kitanidis, "A Kalman filter powered by $$\mathcal{H}^2$$-matrices for quasi-continuous data assimilation problems", Water Resources Research. Preprint*/ Journal version

(6) Sivaram Ambikasaran, "Fast Algorithms for Dense Numerical Linear Algebra and Applications, Stanford Thesis" Official version

(5) Sivaram Ambikasaran, Arvind Krishna Saibaba, Eric Darve, Peter K Kitanidis, "Fast Algorithms for Bayesian Inversion", The IMA Volumes in Mathematics and its Applications Preprint*/ Book chapter

(4) Arvind Krishna Saibaba, Sivaram Ambikasaran, Judith Y Li, Peter K Kitanidis, Eric Darve, "Application of hierarchical matrices in geostatistics", Oil & Gas Science and Technology - Revue d'IFP Energies Nouvelles. Preprint*/ Journal version

(3) Sivaram Ambikasaran, Judith Y Li, Peter K Kitanidis, Eric Darve, "Large-scale stochastic linear inversion using hierarchical matrices", Computational Geosciences. Preprint*/ Journal version

(2) Sivaram Ambikasaran, and Eric Darve, "An $$\mathcal{O}(N \log N)$$ fast direct solver for partially hierarchical semi-separable matrices", Journal of Scientific Computing. Preprint*/ Journal version

(1) K. Bhaskar and Sivaram Ambikasaran, "Untruncated infinite series superposition method for accurate flexural analysis of isotropic/orthotropic rectangular plates with arbitrary edge conditions", Composite Structures. Author copy*/ Journal version

*-Preprints/Author copy are provided for timely dissemination of scholarly and technical work. Also, be aware that the journal version might be little different from the preprint in some cases.

## Research

The group works on theoretical & computational aspects of numerical linear algebra, approximation theory & functional analysis with a focus on constructing highly accurate fast stable algorithms for electromagnetics, elasticity, fluid mechanics, computational statistics, inverse problems and filtering. The overarching goal of the group is to develop robust algorithms founded in rigorous mathematics and convert them into technologies, which inturn can be used as blackbox tools for the aforementioned applications. The broad areas of research are enlisted below.
• ### Numerical & Matrix analysis

• A major facous of our group is on matrix analysis. This broadly includes error analysis, proving stability of algorithms, obtaining error bounds, complexity bounds, etc.
• ### Fast linear algebra algorithms

• Another of the major focusses of the group is to reduce the computational complexity of linear algebra algorithms at the same time maintaining high accuracy.
• #### Dense linear algebra

• Typically, linear algebra algorithms for dense matrix vector products scale as $$\mathcal{O}(N^2)$$ and for solving dense linear systems scale as $$\mathcal{O}(N^3)$$, where the underlying matrix is of size $$N \times N$$. This is excruciatingly slow for large-scale practical problems, making it unattractive for large-scale simulation needed for optimization and design. However, note that since most of the computation is done in finite precision (say machine precision of $$16$$ digits), we can devise approximate but arbitrarily accurate numerical algorithms, that scales favorably and guaranteeing high precision.

• #### Sparse linear algebra

• To solve partial differential equations, discretizing the PDE using finite difference or finite element method is preferred in practice. Such discretizations result in a sparse linear system, which needs to be solved. Solving the corresponding linear system of size $$N \times N$$ using nested dissection or multifrontal strategies requires a computational cost of $$\mathcal{O}(N^{(d+1)/2})$$, where $$d$$ is the underlying dimension. Our focus is on reducing these computational costs to $$\mathcal{O}(N)$$ guaranteeing high precision..
• ### Obstacle scattering

• #### Fast algorithms for scattering

• A major application focus of our lab is on designing accurate, fast electromagnetic solvers for a wide range of applications, for instance, scattering from penetrable and impenetrable objects, advance stealth applications, imaging, etc. Traditional solvers have been mainly based on iterative techniques, which has its own set of disadvantages. For instance, the number of iterations to converge may be extremely large making it impractical. Another disadvantage, especially for design, is that any modifciation to the geometry or incoming field typically results in restarting the entire iterative solver, which is definitely not desirable. To circumvent these disadvantages, our focus is to design high accurate and fast direct solvers for such systems.
• #### Obstacle shape reconstruction

• Another focus, more from an imaging perspective, is to reconstruct the shape of the object from a set of measurements. This becomes more challenging especially when the shape of the underlying object is highly wiggly and also when the measurements are not necessarily what we need.
• ### Fast solvers for homogenization

• One of the goals of homogenization for material scientists is to determine the effective property of the underlying medium. Determining the effective property, relies on solving an elliptic PDE with rapidly varying coefficients. Designing accurate and fast solvers for such challenging problems is another focus of our research group.
• ### Realtime Kalman filtering

• One of the most challenging aspects of dynamical systems and data assimilation is the ability to predict/forecast the state of the system after a certain time. For linear models backed with measurements, Kalman filter provides an optimal filtering algorithm. However, one of the challenges in large scale dynamical systems is the ability to compute and thereby forecast the system.
• ### Computational Statistics

• One of the core issues in computational statistics and large scale data analysis is efficient manipulation of dense covariance matrices, which describe the interdependence between several random variables or random processes. This is espcially the case in spatial statistics and time series. In the previously mentioned contexts, the correlation matrices have a highly exploitable structure.
• ### Black-box tools, reproducible and open source computational science

• There are several implementations of the fast multipole method and fast direct solvers, but very few provide standalone implementations or the basic building blocks" that can be easily re-used. One of our focus is to develop such standalone implementations, which will be of use in many other applications. Another endeavor is to have the tools for computational science available to the public as open source standalone numerical libraries. To this end, we maintain a GitHub repository(https://github.com/sivaramambikasaran) and a GitLab repository (https://gitlab.com/groups/SAFRAN), where all the numerical packages, which include fast multipole method, fast direct solvers, quadratures, etc., developed by us are posted and made available to the public.

## List of possible Research Projects

Below are some of the possible research projects, one can pursue as a member of our group. The list is only indicative and by no means exhaustive.

## Software

All codes are made available in the hope that they will be useful, but without any warranty. All the codes can be redistributed and/or modified under the terms of the appropriate license.
BBFMM2D
- Black Box Fast Multipole Method in two dimensions. Available at: https://github.com/sivaramambikasaran/BBFMM2D
FLIPACK
- Fast Linear Inversion PACKage. Available at: https://github.com/sivaramambikasaran/FLIPACK
HODLR
- Fast Direct Solver for hierarchical off-diagonal low-rank matrices. Available at: https://github.com/sivaramambikasaran/HODLR
ESS
- Extended Semi-Separable algorithm and the generalized Rybicki Press algorithm. Available at: https://github.com/sivaramambikasaran/ESS
George
- fast and flexible Python library for Gaussian Process Regression. Availabe at: http://dan.iel.fm/george/current/
Celerite
- A scalable method for Gaussian Process regression. Available at: http://celerite.readthedocs.io/en/latest/

## Funding

• INSPIRE grant by Department of Science & Technology
• Start-up grant by Indian Institute of Science