A parallel space-time domain decomposition method for unsteady source inversion problems

Xiaomao  Deng; Xiao-Chuan  Cai; Jun Zou

doi:10.3934/ipi.2015.9.1069

Article Contents

2015, Volume 9, Issue 4: 1069-1091. Doi: 10.3934/ipi.2015.9.1069

This issue Previous Article A new Kohn-Vogelius type formulation for inverse source problems Next Article Locally sparse reconstruction using the $l^{1,\infty}$-norm

A parallel space-time domain decomposition method for unsteady source inversion problems

1.
Laboratory for Engineering and Scientific Computing, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong 518055
2.
Department of Computer Science, University of Colorado, Boulder, CO 80309
3.
Department of Mathematics, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong

Received: May 31, 2014

Revised: October 31, 2014

Published: October 2015

Abstract Related Papers Cited by

Abstract

In this paper, we propose a parallel space-time domain decomposition method for solving an unsteady source identification problem governed by the linear convection-diffusion equation. Traditional approaches require to solve repeatedly a forward parabolic system, an adjoint system and a system with respect to the unknown sources. The three systems have to be solved one after another. These sequential steps are not desirable for large scale parallel computing. A space-time restrictive additive Schwarz method is proposed for a fully implicit space-time coupled discretization scheme to recover the time-dependent pollutant source intensity functions. We show with numerical experiments that the scheme works well with noise in the observation data. More importantly it is demonstrated that the parallel space-time Schwarz preconditioner is scalable on a supercomputer with over $10^3$ processors, thus promising for large scale applications.

Keywords:

Mathematics Subject Classification: 65F22, 65F08, 65M60, 65M32, 65M55.

Citation:

Related Papers

Cited by

References

[1]	V. Akcelik, G. Biros, A. Draganescu, O. Ghattas, J. Hill and B. Waanders, Dynamic data-driven inversion for terascale simulations: Real-time identification of airborne contaminants, Proceedings of Supercomputing 2005, Seattle, WA, 2005, p43.doi: 10.1109/SC.2005.25.
[2]	V. Akcelik, G. Biros, O. Ghattas, K. R. Long and B. Waanders, A variational finite element method for source inversion for convective-diffusive transport, Finite Elements in Analysis and Design, 39 (2003), 683-705.doi: 10.1016/S0168-874X(03)00054-4.
[3]	J. Atmadja and A. C. Bagtzoglou, State of the art report on mathematical methods for groundwater pollution source identification, Environmental Forensics, 2 (2001), 205-214.doi: 10.1006/enfo.2001.0055.
[4]	L. Baflico, S. Bernard, Y. Maday, G. Turinici and G. Zerah, Parallel-in-time molecular-dynamics simulations, Physical Review E, 66 (2002), 2-5.
[5]	V. Balakrishnan, All about the Dirac Delta function(?), Resonance, 8 (2003), 48-58.doi: 10.1007/BF02866759.
[6]	S. Balay, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith and H. Zhang, PETSc Users Manual, Technical report, Argonne National Laboratory, 2014.
[7]	A. Battermann, Preconditioners for Karush-Kuhn-Tucker Systems Arising in Optimal Control, Master Thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 1996.
[8]	G. Biros and O. Ghattas, Parallel preconditioners for KKT systems arising in optimal control of viscous incompressible flows, in Parallel Computational Fluid Dynamics 1999, Towards Teraflops, Optimization and Novel Formulations, 2000, 131-138.doi: 10.1016/B978-044482851-4.50017-7.
[9]	X.-C. Cai, S. Liu and J. Zou, Parallel overlapping domain decomposition methods for coupled inverse elliptic problems, Communications in Applied Mathematics and Computational Science, 4 (2009), 1-26.doi: 10.2140/camcos.2009.4.1.
[10]	X.-C. Cai and M. Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM Journal on Scientific Computing, 21 (1999), 792-797.doi: 10.1137/S106482759732678X.
[11]	Z. Chen and J. Zou, An augmented Lagrangian method for identifying discontinuous parameters in elliptic systems, SIAM Journal on Control and Optimization, 37 (1999), 892-910.doi: 10.1137/S0363012997318602.
[12]	P. G. Ciarlet, The Finite Element Method for Elliptic Problems, $1^{st}$ edition, North-Holland Pub. Co., Amsterdam/New York, 1978.
[13]	X. M. Deng, Y. B. Zhao and J. Zou, On linear finite elements for simultaneously recovering source location and intensity, International Journal of Numerical Analysis and Modeling, 10 (2013), 588-602.
[14]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Mathematics and its Applications, 375, Kluwer Academic Publishers Group, Dordrecht, 1996.doi: 10.1007/978-94-009-1740-8.
[15]	C. Farhat and M. Chandesris, Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications, International Journal for Numerical Methods in Engineering, 58 (2003), 1397-1434.doi: 10.1002/nme.860.
[16]	M. J. Gander and E. Hairer, Nonlinear convergence analysis for the parareal algorithm, Domain Decomposition Methods in Science and Engineering XVII, Lect. Notes Comput. Sci. Eng., 60, Springer, Berlin, 2008, 45-56.doi: 10.1007/978-3-540-75199-1_4.
[17]	S. Gorelick, B. Evans and I. Remson, Identifying sources of groundwater pullution: An optimization approach, Water Resources Research, 19 (1983), 779-790.
[18]	E. Haber, A parallel method for large scale time domain electromagnetic inverse problems, Applied Numerical Mathematics, 58 (2008), 422-434.doi: 10.1016/j.apnum.2007.01.017.
[19]	A. Hamdi, The recovery of a time-dependent point source in a linear transport equation: Application to surface water pollution, Inverse Problems, 25 (2009), 075006, 18pp.doi: 10.1088/0266-5611/25/7/075006.
[20]	A. Hamdi, Identification of a time-varying point source in a system of two coupled linear diffusion-advection- reaction equations: Application to surface water pollution, Inverse Problems, 25 (2009), 115009, 21pp.doi: 10.1088/0266-5611/25/11/115009.
[21]	B. Jin and J. Zou, Numerical estimation of the Robin coefficient in a stationary diffusion equation, IMA Journal of Numerical Analysis, 30 (2010), 677-701.doi: 10.1093/imanum/drn066.
[22]	Y. L. Keung and J. Zou, Numerical identifications of parameters in parabolic systems, Inverse Problems, 14 (1998), 83-100.doi: 10.1088/0266-5611/14/1/009.
[23]	Y. L. Keung and J. Zou, An efficient linear solver for nonlinear parameter identification problems, SIAM Journal on Scientific Computing, 22 (2000), 1511-1526.doi: 10.1137/S1064827598346740.
[24]	H. W. Kuhn and A. W. Tucker, Nonlinear programming, in Proceedings of 2nd Berkeley Symposium, University of California Press, Berkeley, 1951, 481-492.
[25]	J.-L. Lions, Y. Maday and G. Turinici, A "parareal" in time discretization of PDEs, ComptesRendus de l'Academie des Sciences Series I Mathematics, 332 (2001), 661-668.doi: 10.1016/S0764-4442(00)01793-6.
[26]	X. Liu, Identification of Indoor Airborne Contaminant Sources with Probability-Based Inverse Modeling Methods, Ph.D. Thesis, University of Colorado, 2008.
[27]	X. Liu and Z. Zhai, Inverse modeling methods for indoor airborne pollutant tracking literature review and fundamentals, Indoor Air, 17 (2007), 419-438.doi: 10.1111/j.1600-0668.2007.00497.x.
[28]	Y. Maday and G. Turinici, Parallel in time algorithms for quantum control: Parareal time discretization scheme, International Journal of Quantum Chemistry, 93 (2003), 223-228.doi: 10.1002/qua.10554.
[29]	Y. Maday and G. Turinici, The parareal in time iterative solver: A further direction to parallel implementation, in Domain Decomposition Methods in Science and Engineering, Lect. Notes Comput. Sci. Eng., 40, Springer, Berlin, 2005, 441-448.doi: 10.1007/3-540-26825-1_45.
[30]	G. Nunnari, A. Nucifora and C. Randieri, The application of neural techniques to the modelling of time-series of atmospheric pollution data, Ecological Modelling, 111 (1998), 187-205.doi: 10.1016/S0304-3800(98)00118-5.
[31]	E. Prudencio, R. Byrd and X.-C. Cai, Parallel full space SQP Lagrange-Newton-Krylov-Schwarz algorithms for PDE-constrained optimization problems, SIAM Journal on Scientific Computing, 27 (2006), 1305-1328.doi: 10.1137/040602997.
[32]	R. Revelli and L. Ridolfi, Nonlinear convection-dispersion models with a localized pollutant source II-a class of inverse problems, Mathematical and Computer Modelling, 42 (2005), 601-612.doi: 10.1016/j.mcm.2004.06.023.
[33]	Y. Saad, Iterative Methods for Sparse Linear Systems, $2^{nd}$ edition, Society for Industrial and Applied Mathematics, 2003.doi: 10.1137/1.9780898718003.
[34]	A. Samarskii and P. Vabishchevich, Numerical Methods for Solving Inverse Problems of Mathematical Physics, Walter de Gruyter, Berlin, 2007.doi: 10.1515/9783110205794.
[35]	T. Skaggs and Z. Kabala, Recovering the release history of a groundwater contaminant, Water Resources Research, 30 (1994), 71-79.doi: 10.1029/93WR02656.
[36]	T. Skaggs and Z. Kabala, Recovering the history of a groundwater contaminant plume: Method of quasi-reversibility, Water Resources Research, 31 (1995), 2669-2673.doi: 10.1029/95WR02383.
[37]	M. Snodgrass and P. Kitanidis, A geostatistical approach to contaminant source identification, Water Resources Research, 33 (1997), 537-546.doi: 10.1029/96WR03753.
[38]	G. Staff and E. Ronquist, Stability of the parareal algorithm, in Domain Decomposition Methods in Science and Engineering, Lect. Notes Comput. Sci. Eng., {40}, Springer, Berlin, 2005, 449-456.doi: 10.1007/3-540-26825-1_46.
[39]	A. Toselli and O. Widlund, Domain Decomposition Methods-Algorithms and Theory, Springer, 2005.
[40]	J. Wong and P. Yuan, A FE-based algorithm for the inverse natural convection problem, International Journal for Numerical Methods in Fluids, 68 (2012), 48-82.doi: 10.1002/fld.2494.
[41]	A. Woodbury, Inverse Engineering Handbook, CRC Press, 2003.
[42]	J. L. Xie and J. Zou, Numerical reconstruction of heat fluxes, SIAM Journal on Numerical Analysis, 43 (2005), 1504-1535.doi: 10.1137/030602551.
[43]	C. Yang, J. Cao and X.-C. Cai, A fully implicit domain decomposition algorithm for shallow water equations on the cubed-sphere, SIAM Journal on Scientific Computing, 32 (2010), 418-438.doi: 10.1137/080727348.
[44]	H. Yang, E. Prudencio and X.-C. Cai, Fully implicit Lagrange-Newton-Krylov-Schwarz algorithms for boundary control of unsteady incompressible flows, International Journal for Numerical Methods in Engineering, 91 (2012), 644-665.doi: 10.1002/nme.4286.
[45]	X. Zhang, C. X. Zhu, G. D. Feng, H. H. Zhu and P. Guo, Potential use of bacteroidales specific 16S rRNA in tracking the rural pond-drinking water pollution, Journal of Agro-Environment Science, 30 (2011), 1880-1887.
[46]	B. Q. Zhu, Y. W. Chen and J. H. Peng, Lead isotope geochemistry of the urban environment in the Pearl River Delta, Applied Geochemistry, 16 (2001), 409-417.