The main goal of this project is to design and implement fast algorithms for the solution of inverse problems constrained by elliptic and parabolic partial differential equations (PDEs) on regular domains. Our main motivation is the application of these algorithms for inverse problems in electro-cardiography. We considered the following two formulations: (1) an elliptic source inversion problem, and (2) a parabolic source inversion problem in which the sources are time-independent. These problems are formulated as PDE-constrained optimization problems and Tikhonov regularization is used in both the problems for stability. We used the reduced space approach in which we eliminate the state and the adjoint variables and we iterate in the inversion parameter space using Conjugate Gradients (CG). We derived the Singular Value Decomposition (SVD) of the Hessian analytically and designed preconditioners to accelerate the convergence of CG when applied to the elliptic source inversion problem. The overall complexity of reconstructing the source is [Special characters omitted.] ( N log N ), where N is the number of parameters used to represent the source. We derived analytical expressions for the entries of the Hessian and proposed multigrid and low rank Hessian approximation preconditioners to accelerate the convergence of CG to solve the parabolic source inversion problem. The overall complexity of solving the parabolic source inversion problem in the case of domain observations and boundary observations is [Special characters omitted.] ( N t N + N log 2 N ) and [Special characters omitted.] ( N t N log N ) respectively, where N is the number of parameters to represent the source and N t is the number of time steps. We showed that these methods are algorithmically robust to the value of the regularization parameter using numerical experiments, and thus, useful for the cases in which we seek high-fidelity reconstructions. We have observed that we cannot reconstruct the sources completely by solving the elliptic source inversion problem using the boundary data. On the other hand, by solving the parabolic source inversion problem using the boundary data we have observed an accurate reconstruction of source. We have solved a 3D parabolic source inversion problem with 2 million inversion variables and 0.2 billion state variables on 32 processors in 6 minutes.
