research
sparse matrix algorithms and software
The large matrices that arise in real-world problems in science, engineering, and mathematics tend to be mostly zero, or sparse. Sparse matrix algorithms lie in the intersection of graph theory and numerical linear algebra. A graph represents the connections between variables in the mathematical model, such as the voltage across a circuit component, a link from one web page to another, the physical forces between two points in a mechanical structure, and so on, depending on the problem at hand. The numerical linear algebra arises because these matrices represent systems of equations whose solution tells us something about how the real-world problem behaves. Google’s page rank algorithm, for example, requires the computation of an eigenvector for a matrix with as many rows and columns as there are pages on the web.
My research spans the spectrum of theory, algorithms, and software development in the area of sparse matrix and graph algorithms. I’m not just interested in creating new methods and software prototypes to demonstrate those methods. I pursue the code further to produce better-than-commercial-quality software that embodies these new methods. Nine of my codes appear as Collected Algorithms of the ACM, where they undergo rigorous peer-review testing for their research contributions and software quality.
I just love to delve into the theory and algorithms of graph theoretic and applied mathematical algorithms, but I don’t stop there. I just love to code. I collaborate with others with the same passion -- and I hope to instill the same drive in my students (graduate and undergraduate).
NASA once performed a software engineering exercise in which they used the most extreme techniques to produce the highest quality code they could create. With a fault rate of 0.1 KLOC, they concluded that such reliability is achievable but not practical. The MathWorks utilizes about 120K lines of my codes in MATLAB: x=A\b when A is sparse, sparse factorization methods (LU, QR, and Cholesky), sparse matrix multiplication, Dulmage-Mendelsohn decomposition, and fill-reducing orderings. If printed out, 120K lines of code would equal about 2 reams of paper, front and back. With only 3 bugs reported in my codes used in MATLAB in 15 years, this reliability metric out-performs NASA’s best-achievable result by a factor of 3.
My codes are also fast (in both senses of the word: asymptotically and in practice). For example, the time to factorize a benchmark matrix from the European Space Operations Center (for tracking orbital debris) dropped from 11 days to 7 minutes when my QR factorization method was added to MATLAB.
FUTURE VISION
The coming decades of high-performance computational mathematics will be increasingly dominated by heterogeneous computing based on hybrid multiprocessors with of a mix of conventional CPU cores and high-throughput GPU cores. This trend is driven by power constraints and the need for ever-increasing performance. Although these new heterogeneous systems can deliver high performance with low energy requirements, new algorithms must be developed to exploit them. The most challenging problems for these systems require a mix of regular and irregular computation. My research into direct methods for sparse linear systems lies within this problem domain and is also a critical component for many applications in computational mathematics.
My experience makes me well-poised for future research in GPU-based algorithms. As a world leader in algorithmic research for sparse matrix computations, my work combines graph-theoretic methods and numerical techniques to create algorithms for solving problems in computational science that arise across a wide range of applications. I incorporate my novel theory and algorithms into robust library-quality open-source software, which is widely used in industry, academia, and government labs. In the past decade, I have published more software in the ACM Transactions on Mathematical Software than any other author.
A primary thrust for my current and future work focuses on creating parallel algorithms for sparse multifrontal LU, QR, and Cholesky factorization for hybrid multicore CPU/GPU multiprocessors. The workflow in these algorithms is an irregular tree, where the nodes are the bulk of the work (regular operations on dense frontal matrices of varying sizes), and the edges are the irregular assembly of data from child to parent. The GPUs operate on many frontal matrices at a time, and data is assembled from child to parent frontal matrix without moving it to the CPU. No other sparse direct method employs these strategies for GPU computing. By creating widely-used high-performance algorithms and software that encapsulate these ideas, this research will extend the capability of heterogeneous computing to a wide domain of applications in computational science and mathematics.
Below is a talk that summarizes much of my research. Click here for the slides.
Google relies my code in Ceres, their nonlinear solver. They use this to place every photo in its correct position for Google Street View, to create Google Photo Tours, and for 3D imagery in Google Earth. Below are some samples of Ceres (and thus SuiteSparse) at work. Without SuiteSparse, Ceres wouldn’t be able to do its job, and Google Street View would be a lesser experience as a result.
CURRENT SPONSORS
SuiteSparse ON linux or Mac
APPLICATIONS
My software is so widely used that I can’t keep track of its usage. You can get a glimpse of this yourself via simple Google searches for some of the unique names of my solvers, for example: COLAMD, SuiteSparse, UMFPACK, and CHOLMOD.
Some of the specific uses of my solvers in industry, government labs, and academia are listed below. This is a partial list since I don’t require registration of any kind for you to use my codes. If you are using my codes and would like a link to appear below, just drop me a line.
companies / commercial software
The MathWorks (MATLAB): general toolbox for scientific computation
Wolfram Research (Mathematica; also here or here):
general toolbox for scientific computation
Google Ceres (used by Street View): nonlinear least squares solver
Facebook: Oculus
Cadence Design Systems (OrCAD and Allegro): circuit simulation
IBM: circuit simulation
ANSYS: finite-element method
Apple
Berkeley Design Automation (their "fast sparse-matrix solver" is KLU):
circuit simulation
Geomodeling Solutions: geological modeling
MSC Software (NASTRAN): finite-element method
Orcina: structural modeling
ATopTech: circuit simulation
Tandent Vision: computer vision
Vision Map: computer vision
EnerNex: energy simulation
FEAT: finite-element method
Freescale: semiconductor simulation
Geograf: geophysical modeling
HRL Laboratories: circuit simulation
Intex: financial simulation
Lumerical: circuit simulation
Mentor Graphics: circuit simulation
SIMetrix: circuit simulation
COMSOL (FEMLAB): finite-element method
NVIDIA (CULA sparse): sparse matrix library for GPUs
WRSpice: circuit simulation
AgiSoft: PhotoScan - photogrammetric processing of images into 3D spatial data
Embotech: ECOS embedded conic solver
Government labs
HSL Mathematical Subroutine Library: general library for computational science
Xyce by Sandia National Labs: circuit simulation
Knolls Atomic Power Lab: nuclear reactor design
PETsc by Argonne National Lab: general toolbox for computational science
Amesos and Trilinos by Sandia National Labs:
general toolbox for computational science
FiPy by NIST: finite-element method
ISIS by USGS: astrogeology image processing (Moon, Mars, Mercury, ...)
ARKcode: ODE solver, part of SUNDIALS, by Lawrence Livermore National Lab
academia / open source
Google Ceres (used by Street View): nonlinear least squares solver
GEGL (used in Gimp): graphics/image processing
Julia: programming language with built-in support for sparse matrices
SuperLU: sparse matrix library
MUMPS: sparse matrix library
Fedora Linux: general math library distribution for Linux
Debian Linux: ditto
Arch Linux: ditto
Ubuntu Linux: ditto
OpenSUSE Linux: ditto
Scientific Linux: ditto
GNU Darwin: general math library distribution for MacOS X
DarwinPorts: ditto
Homebrew: ditto
Fink: ditto
Octave: general toolbox for computational science
R: statistical package
ROS: robot operating system
deal.II: finite-element method / differential equations library
scilab: general toolbox for computational science
CVX: convex optimization
CVXPY: Python package for convex optimization
SDPT3: semidefinite quadratic linear programming
CVXOPT: convex optimization
MBDyn: multi-body dynamics
Boost: C++ libraries
OpenSees: earthquake simulation
umfpackpy: Python bindings for UMFPACK
CGAL: computational geometry algorithms library
Kraken: Cray XT5 installation
FEniCS Project: differential equations
Eigen: general toolbox for computational science
Sage: Python-based mathematics software system
SciPy: Python-based software for mathematics, science, and engineering
NumPy: fundamental matrix computations for Python (see also SciPy).
SciPy.sparse: sparse matrix library for Python
Pysparse: sparse matrix library for Python
NLPy: nonlinear programming in Python
SfePy: finite-element method in Python
FreeFem++: finite-element method
Elmer: finite-element method
FLOODS/FLOOPS: semiconductor device/process modeling
MILAMIN: finite-element method
Minimum Sobolev Norm-based Methods for Elliptic PDEs, to appear.
ILUPACK: ILU preconditioning package.
JADAMILU: sparse eigenvector package.
Cubica: non-linear finite-element package.
LAMG: algebraic multigrid solver
LiveV: finite-element method
M.E.S.S: sparse solvers, model order reduction, optimal control.
AMDisS: finite-element toolbox
PDCO: primal-dual interior method for convex optimization
MLD2P4: parallel algebraic multi-level preconditioners
FEATFLOW: finite-element method
FEAST: finite-element method
OpenSLAM: robotics projects; 10 of 24 use sparse solvers (all in SuiteSparse):
g2o: optimization of graph-based nonlinear error functions. Their use of
CHOLMOD is notable because they rely on our optimal sparse Cholesky
update/downdate methods. Other packages: 2D-I-SLSJF, HOG-Man,
RobotVision, SLAM6D, SSA2D, MTK, SLOM, iSAM, TJTF
LSD-SLAM: large-scale direct monocular SLAM
SSBA: sparse bundle adjustment
libdogleg: large-scale nonlinear least-squares optimization
CUSPICE, a CUDA-accelerated NGSPICE: circuit simulation
A splitting method for optimal control
hpFEM/Hermes: finite-element toolbox
PATH solver: optimization package for mixed complementarity problems
MESA: stellar evolution
DSM2: California Bay Delta Simulation Model II
Caphe: optical circuit simulation
GLPK: GNU Linear Programming Kit
libdogleg: general purpose sparse optimizer to solve data fitting problems
iSAM: incremental Smoothing and Mapping for the SLAM (robotics) problem
also iSAM2.
GTSAM: the SLAM problem for autonomous flying vehicles
DOLFIN: automated finite element computing
OPM: Open Porous Media Project
MFEM: finite element solver
the SUITEsparse matrix collection
I also collect matrices from real applications (like those above) and make them available as benchmarks to researchers in sparse matrix algorithms and graph / network algorithms. They are incredibly useful because randomly generated matrices tend not to capture the structure of matrices that arise in practice. If you develop a method and test it with random problems, it will likely behave very differently when used in practice, on real problems.
The collection is now located at https://sparse.tamu.edu.
To maintain this collection, I collaborate with Yifan Hu at Yahoo! labs, who develops visualization techniques. These matrices are not only scientifically useful, they are beautiful as well. Below is a small sample (click here for the full collection).
COLLABORATORS
Iain Duff
John Gilbert
Esmond Ng
Patrick Amestoy
Bill Hager
Ekanathan Natarajan Palamadai
Stefan Larimore
Siva Rajamanickam
Yanqing Chen
Les Foster
Sanjay Ranka
Nuri Yeralan
Sharanyan Chetlur
Anil Rao
Begum Senses
Yifan Hu
Steve Rennich
Wissam Sid-Lakhdar
major users
SIAM plenary talk at the 2006 SIAM Annual Meeting. This talk gives an accessible introduction to my research, and serves as an overview of my graduate-level course on sparse matrix algorithms. Click here for the slides.