Software

This part is research code, each of them is attached to my research publications.

FastBF [github]

Fast Butterfly Factorization, which is also known as the interpolative butterfly factorization (IBF), gives a data-sparse representation of matrices that satisfy the complementary low-rank property. Given the explicit expression of the kernel, IBF factorizes the kernel matrix in $\mathcal{O}(N\log N)$ operations. And the final factorization admits $\mathcal{O}(N\log N)$ operations and memory complexity with nearly optimal prefactor. This code supports the interpolative butterfly factorization of any dimensional problems with and without singularity. Several examples are provided in the test folders. This is joint work with Haizhao Yang.

BF [github]

Butterfly Factorization (BF) gives a data-sparse representation of matrices that satisfy the complementary low-rank property. The factorization approximates such a kernel matrix of size $N\times N$ with a product of $\mathcal{O}(\log N)$ sparse matrices, each of which contains $\mathcal{O}(N)$ nonzero entries. Hence the application only requires $\mathcal{O}(N\log N)$ operations and memory. This code supports the butterfly factorization of $d$ dimensional matrices for $d\leq 2$. Several examples are provided in the test folders. This is joint work with Haizhao Yang, Eileen Martin (one dimensional code), Kenneth L. Ho (one dimensional code), and Lexing Ying.

MBA [github]

Multiscale Butterfly Algorithm (MBA) is a code for the fast evaluation of Fourier Integral Operators (FIOs). Both 2D and 3D FIOs can be fast evaluated via this code. Several examples are provided in the test folders. This is joint work with Haizhao Yang and Lexing Ying.

DMHM [bitbucket]

Distributed-Memory Hierarchical Matrices (DMHM) is a code for mpi based hierarchical matrix algebra. This code support both 2D and 3D $\mathcal{H}$-matrices. $\mathcal{H}$-matrix application, composition, addition and inversion are completed. This is joint work with Jack Poulson and Lexing Ying.

Code

This part is research related code, while none of them is attached to any specific paper.

MuFiM [github]

MuFiM is code for the MultiFrontal method for general sparse matrices in Matlab. This code currently supports the fast factorization of symmetric matrices, Hermitian matrices, and pattern symmetric matrices. The complexity analysis of the algorithm is available if the sparse matrix is discretized from PDEs with a local numerical scheme. For two-dimensional problems, the factorization and solving/application are of complexities $\mathcal{O}(N^{3/2})$ and $\mathcal{O}(N\log N)$ respectively. For three-dimensional problems, the factorization and solving/application are of complexities $\mathcal{O}(N^2)$ and $\mathcal{O}(N^{4/3})$ respectively. The factorization phase of MuFiM is about 4 times slower than Matlab default "/" or "\" operation. While once the factors are available, the solving/application is of lower complexity than Matlab default solving. In practice, the running time is also much faster.

meshpart [github]

Meshpart is a Matlab toolbox for several graph and mesh partitioning methods, including geometric, spectral, geometric spectral, and coordinate bisections. It also has routines to generate recursive multiway partitions, vertex separators, and nested dissection orderings. It functions similar to MetisMex, but purely in Matlab. This is joint work with John R. Gilbert and Shang-Hua Teng.

MetisMex [github]

Metis Mex is mex files for METIS. This code currently supports 64-bit Linux and Mac. If any support for 32-bit computer or PC is needed, please email me.

FastSpecialMat [github]

Fast Special Matrices is code for fast application of special matrices. This code currently supports the fast application of circulant matrices, Hankel matrices, Hankel circulant matrices, Toeplitz matrices and Toeplitz symmetric matrices. The complexities of all these applications are $\mathcal{O}(N \log N)$ for $N$ by $N$ matrices.