MULTIGRID ALGORITHMS FOR INVERSE PROBLEMS WITH LINEAR PARABOLIC PDE CONSTRAINTS

被引:18
作者
Adavani, Santi S. [1 ]
Biros, George [1 ,2 ,3 ]
机构
[1] Univ Penn, Dept Mech Engn & Appl Mech, Philadelphia, PA 19104 USA
[2] Univ Penn, Dept Bioengn, Philadelphia, PA 19104 USA
[3] Univ Penn, Dept Comp & Informat Sci, Philadelphia, PA 19104 USA
基金
美国国家科学基金会;
关键词
inverse problems; heat equation; reaction-diffusion equations; multigrid; regularization;
D O I
10.1137/070687426
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We present a multigrid algorithm for the solution of source identification inverse problems constrained by variable-coefficient linear parabolic partial differential equations. We consider problems in which the inversion variable is a function of space only. We consider the case of L-2 Tikhonov regularization. The convergence rate of our algorithm is mesh-independent-even in the case of no regularization. This feature makes the method algorithmically robust to the value of the regularization parameter, and thus useful for the cases in which we seek high-fidelity reconstructions. The inverse problem is formulated as a PDE-constrained optimization. We use a reduced-space approach in which we eliminate the state and adjoint variables, and we iterate in the inversion parameter space using conjugate gradients. We precondition the Hessian with a V-cycle multigrid scheme. The multigrid smoother is a two-step stationary iterative solver that inexactly inverts an approximate Hessian by iterating exclusively in the high-frequency subspace (using a high-pass filter). We analyze the performance of the scheme for the constant coefficient case with full observations; we analytically calculate the spectrum of the reduced Hessian and the smoothing factor for the multigrid scheme. The forward and adjoint problems are discretized using a backward-Euler finite-difference scheme. The overall complexity of our inversion algorithm is O(NtN + N log(2) N), where N is the number of grid points in space and N-t is the number of time steps. We provide numerical experiments that demonstrate the effectiveness of the method for different diffusion coefficients and values of the regularization parameter. We also provide heuristics, and we conduct numerical experiments for the case with variable coefficients and partial observations. We observe the same complexity as in the constant-coefficient case. Finally, we examine the effectiveness of using the reduced-space solver as a preconditioner for a full-space solver.
引用
收藏
页码:369 / 397
页数:29
相关论文
共 30 条
[1]  
Akcelik V., 2005, P 2005 ACM IEEE C SU
[2]  
ARIAN E, 1994, NASACR194939 I COMP
[3]  
ARIOLI M, 2002, RALTR2002021 ATL CTR
[4]  
Axelsson O., 1994, ITERATIVE SOLUTION M
[5]  
Banks H. T., 1989, ESTIMATION TECHNIQUE
[6]  
Benzi M, 2005, ACTA NUMER, V14, P1, DOI 10.1017/S0962492904000212
[7]   Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver [J].
Biros, G ;
Ghattas, O .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2005, 27 (02) :687-713
[8]   Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part II: The Lagrange-Newton solver and its application to optimal control of steady viscous flows [J].
Biros, G ;
Ghattas, O .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2005, 27 (02) :714-739
[9]   Experiences with a space-time multigrid method for the optimal control of a chemical turbulence model [J].
Borzì, A ;
Griesse, R .
INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN FLUIDS, 2005, 47 (8-9) :879-885
[10]   Multigrid methods for parabolic distributed optimal control problems [J].
Borzì, A .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2003, 157 (02) :365-382