1997 — 2002 
Gu, Ming 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Career: Algorithms For Eigenvalue and Singular Value Problems @ University of CaliforniaLos Angeles
The research part of this CAREER project develops accurate and efficient numerical methods for a number of important problems including high relative accuracy (tiny percentage error) eigenvalue and singular value computations, updating the singular value decomposition (SVD), and distance problems in linear systems and control computations. Although current methods for solving them are abundant, many important questions remain unanswered. For example, a large number of recent papers describe numerical methods to compute all eigenvalues and singular values to high relative accuracy for a few isolated special classes of matrices, but a common explanation and a common numerical method are missing. As another example, the ability to rapidly update the SVD is critical in signal processing applications since problems are often real time, but none of the current methods is efficient enough for this purpose. A goal is to provide a common explanation and a common numerical method for high relative accuracy eigenvalue and singular value computations. It turns out that the common explanation and common numerical method are applicable to many new interesting classes of matrices, arising from areas as diverse as combinatorics and numerical solution of ODE's and PDE's. The project also aims at providing rapid methods for updating the SVD, hence removing a major bottleneck in SVDbased methods for various signal processing applications. The education part of the project is to develop software tools so that students taking abstract mathematics courses can clearly envision and play with the sometimes abstract objects and results on the WorldWide Web with vivid graphical display. The plan also includes new graduate courses in numerical linear algebra with scientific and engineering applications.

0.976 
2002 — 2006 
Gu, Ming 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Fast Numerically Stable Matrix Algorithms @ University of CaliforniaBerkeley
ABSTRACT 0204388 Ming Gu U of Calif  Berkeley
The San Andreas Fault zone Observatory at Depth (SAFOD) Pilot Hole will provide an excellent opportunity for exploring the relationship between fault slip and the thermal evolution of the crust by studying core samples from varying depths using two complementary thermochronologic methods. The Pilot Hole, located in Parkfield less than two kilometers from the San Andreas fault will reach a depth of 2.1 km. The borehole will intersect Salinian granitic rocks at a depth of less than 1 km and similar granitic rocks outcrop at the surface within a few kilometers of the Pilot Hole. We will analyze samples from borehole cuttings at depth intervals of 100  200 m and from the surface outcrops. We will determine the thermal history of the samples using apatite fission track and U/ThHe thermochronometers.

1 
2005 — 2009 
Gu, Ming 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Collaborative Research: SuperFast Direct Sparse Solvers @ University of CaliforniaBerkeley
ABSTRACT 051034 Ming Gu U of California  Berkeley
Collaborative Research: Superfast direct sparse solvers
The numerical solution of partial differential equations (PDE) is a key enabling technology in all disciplines of engineering and science. Nevertheless the numerical solution of threedimensional PDEs is a critical bottleneck that prevents this potential from being realized. This proposal advances techniques that can be used to overcome this bottleneck. Discretized elliptic PDEs are normally solved by iterative schemes since the fillin during sparse Gaussian elimination is excessive. This proposal observes that the fillin, in a certain ordering, has low numerical rank in the offdiagonal blocks, and that this structure can be computed and exploited to construct direct solvers that are linear in the number of unknowns. The outcome of the proposed research has the potential to create a novel class of preconditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult elliptic PDEs. The intellectual merit of the proposal stems from the complicated structure in the fillin that must be first inferred from regularity results for Green's functions in elliptic PDE theory and then converted into effective lineartime algorithms to both capture the structure on the fly during sparse Gaussian elimination, and then exploited to speed up the very same Gaussian elimination. The impact of the proposal will be to provide new solvers for difficult PDEs. In particular thesoftware that is developed will be made available to the community, and should enable scientists and engineers to have a new tool for their difficult problems. It will also infuse fresh ideas into the field of sparse direct solvers and unify it with the field of iterative methods.

1 
2008 — 2013 
Gu, Ming 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Collaborative Research: Minimum Sobolov Norm Methods @ University of CaliforniaBerkeley
Collaborative Research: Minimum Sobolev Norm Methods
The aim of this research project is to design fast and accurate numerical algorithms for the solution of large classes of mathematical equations that arise in engineering and science. In particular, the main concerns are the solution of integrodifferential equations on complex domains and of signal and image processing problems. The approach is based on formulating the estimate of the solution of the equation at a point as the value of the smoothest solution (on average) at that point based on the given data. The resulting discrete equations can be shown to have specially structured matrices, which can be exploited to create fast solvers for these equations. The resulting methods have two main computational advantages. First, they can be designed to avoid gridding or triangulation of the complex domain. Second, these methods exhibit local convergence; that is, the rate at which the approximant converges to the solution at a point depends only on the local smoothness of the solution. These advantages enable the method to tackle equations with complicated singularity structures with relative ease.
Let Hs denote a Sobolev Hilbert space whose elements have s > 1 fractional derivatives. Suppose an unknown function f in Hs satisfies the equation L(F) = g, where L is a linear operator and g is a known function. Let Ln denote n linear functionals on Hr. Let q denote a linear functional on Hs. Then the best minmax estimate for q(f) can be computed from the minimum Sobolev norm function p in Hs that satisfies the constraints Ln(L(p)) = Ln(g). This p can be computed very rapidly since the optimal p is given by a nice set of equations that has Fast Multipole Method (FMM) structure when written in the proper representation. Also, it is possible to work with Lp Sobolev spaces with p = 1. In these cases the optimization problem is more complicated and can be reduced to linear programming problems, for which fast solvers are being developed that exploit the underlying FMM structure of the constraint matrix. The theoretical work consists of studying the convergence of the solution as n gets bigger, and also in proving the FMM structure of the resulting discrete equations. The algorithmic work consists of designing fast algorithms for constructing the FMM representation and then designing fast algorithms for the direct (noniterative) solution of these equations. The application work consists of applying these ideas to image segmentation and multirate signal processing. Also, mesh free, locally convergent schemes are being developed for the solution of integral equations and elliptic partial differential equations on complex domains in two dimensions.

1 
2013 — 2017 
Gu, Ming 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
"Af:Small:Efficient and Reliable LowRank Approximation Techniques and Fast Solutions to Large Sparse Linear Equations" @ University of CaliforniaBerkeley
In many computational and engineering problems, it is critical to solve large sparse linear systems of equations rapidly and reliably. Nevertheless, many practical but difficult large linear systems of equations remain out of reach computationally. In this project, the PI develops structured fast direct methods and preconditioners for solving such large sparse linear systems. These methods systematically exploit potentially rich numerical lowrank patterns within the fillins for large reductions in computational time and memory. The efficiency of these methods comes from three innovative design strategies: the PI develops randomized algorithms that can rapidly compute high quality lowrank approximations with low numerical compression overhead; the PI adapts these methods to preserve desirable properties of the original matrix for enhanced numerical reliability; and the PI reorganizes the computations so that no numerical compression and data communication is performed unless necessary.
The outcome of this research has the potential to create a novel class of direct solvers and preconditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult large sparse linear systems, and the lowrank approximation schemes would become a valuable tool for the general scientific community, as effective data compression is essential in many areas of science and engineering. Mathematical software for rapidly solving large sparse linear systems of equations and for effective compression of large data sets will be made available to the scientific computing public.

1 