A scalable space-time domain decomposition approach for solving large scale nonlinear regularized inverse ill posed problems in 4D variational data assimilation. (English) Zbl 1494.90048
Summary: We address the development of innovative algorithms designed to solve the strong-constraint Four Dimensional Variational Data Assimilation (4DVar DA) problems in large scale applications. We present a space-time decomposition approach which employs the whole domain decomposition, i.e. both along the spacial and temporal direction in the overlapping case, and the partitioning of both the solution and the operator. Starting from the global functional defined on the entire domain, we get to a sort of regularized local functionals on the set of sub domains providing the order reduction of both the predictive and the Data Assimilation models. The algorithm convergence is developed. Performance in terms of reduction of time complexity and algorithmic scalability is discussed on the Shallow Water Equations on the sphere. The number of state variables in the model, the number of observations in an assimilation cycle, as well as numerical parameters as the discretization step in time and in space domain are defined on the basis of discretization grid used by data available at repository Ocean Synthesis/Reanalysis Directory of Hamburg University.
MSC:
| 90C06 | Large-scale problems in mathematical programming |
| 90C90 | Applications of mathematical programming |
Keywords:
data assimilation; space and time decomposition; scalable algorithm; inverse problems; nonlinear least squares problemsReferences:
| [1] | Antil, H.; Heinkenschloss, M.; Hoppe, RH; Sorensen, DC, Domain decomposition and model reduction for the numerical solution of PDE constrained optimization problems with localized optimization variables, Comput. Vis. Sci., 13, 6, 249-264 (2010) · Zbl 1220.65074 · doi:10.1007/s00791-010-0142-4 |
| [2] | Amaral, S.; Allaire, D.; Willcox, K., A decomposition-based approach to uncertainty analysis of feed-forward multicomponent systems, Int. J. Numer. Methods Eng., 100, 13, 982-1005 (2014) · Zbl 1352.93016 · doi:10.1002/nme.4779 |
| [3] | Arcucci, R., D’Amore, L., Pistoia, J., Toumi, R., Murli, A.: On the variational data assimilation problem solving and sensitivity analysis. J. Comput. Phys. 335, 311-326 (2017) · Zbl 1375.49036 |
| [4] | Arcucci, R., D’Amore, L., Carracciuolo, L., Scotti, G., Laccetti, G.: A decomposition of the tikhonov regularization functional oriented to exploit hybrid multilevel parallelism. J. Parallel Program. 45(5), 1214-1235 (2017) |
| [5] | Clerc, S.: Etude de schemas decentres implicites pour le calcul numerique en mecanique des fluides, resolution par decomposition de domaine. Ph.D. thesis, Univesity Paris VI (1997) |
| [6] | Constantinescu, E., D’Amore L.: A mathematical framework for domain decomposition approaches in 4D VAR DA problems. H2020-MSCA-RISE-2015-NASDAC project, Report 12-2016, doi:10.13140/RG.2.2.34627.20002 |
| [7] | D’Amore, L., Arcucci, R., Carracciuolo, L., Murli, A.: A scalable approach to three dimensional variational data assimilation. J. Sci. Comput. (2014). doi:10.1007/s10915-014-9824-2 · Zbl 1311.65056 |
| [8] | Daget, N.; Weaver, AT; Balmaseda, MA, Ensemble estimation of background-error variances in a three-dimensional variational data assimilation system for the global ocean, Q. J. R. Meteorol. Soc., 135, 1071-1094 (2009) · doi:10.1002/qj.412 |
| [9] | D’Amore, L., Arcucci, R., Carracciuolo, L., Murli, A.: A scalable variational data assimilation. J. Sci. Comput. 61, 239-257 (2014) · Zbl 1311.65056 |
| [10] | D’Amore, L., Laccetti, G., Romano, D., Scotti, G.: Towards a parallel component in a GPU-CUDA environment: a case study with the L-BFGS Harwell routine. J. Comput. Math. 93(1), 59-76 (2015) · Zbl 1308.65227 |
| [11] | D’Amore, L., Carracciuolo, L., Constantinescu, E.: Validation of a PETSc based software implementing a 4DVAR data assimilation algorithm: a case study related with an oceanic model based on shallow water equation. Oct. 2018 arXiv:1810.01361v2 |
| [12] | Dennis, JE Jr; Moré, JJ, Quasi-Newton methods, motivation and theory, SIAM Rev., 19, 1, 46-89 (1977) · Zbl 0356.65041 · doi:10.1137/1019005 |
| [13] | Dennis, JE Jr; Schnabel, RB, Numerical Methods for Unconstrained Optimization and Nonlinear Equation (1996), Philadelphia: SIAM, Philadelphia · Zbl 0847.65038 · doi:10.1137/1.9781611971200 |
| [14] | Emmett, M.; Minion, ML, Toward an efficient parallel in time method for partial differential equations, Commun. Appl. Math. Comput. Sci., 7, 105-132 (2012) · Zbl 1248.65106 · doi:10.2140/camcos.2012.7.105 |
| [15] | ECMWF Ocean ReAnalysis ORA-S3. Avalaible to: http://icdc.cen.uni-hamburg.de/projekte/easy-init/easy-init-ocean.html |
| [16] | Fischer, M., Gurol, S.: Parallelization in the time dimension of the four dimensional variational data assimilation. doi:10.1002/qj:2996 |
| [17] | Flatt, HP; Kennedy, K., Performance of parallel processors, Parallel Comput., 12, 1-20 (1989) · Zbl 0734.68019 · doi:10.1016/0167-8191(89)90003-3 |
| [18] | Gander, MJ; Carraro, T.; Geiger, M.; Körkel, S.; Rannacher, R., 50 years of time parallel time integration, Multiple Shooting and Time Domain Decomposition Methods: MuS-TDD, 69-113 (2015), Heidelberg: Springer International Publishing, Heidelberg · Zbl 1337.65127 · doi:10.1007/978-3-319-23321-5_3 |
| [19] | Gander, MJ; Kwok, F., Schwarz methods for the time-parallel solution of parabolic control problems, Lect. Notes Comput. Sci. Eng., 104, 207-216 (2016) · Zbl 1369.65080 · doi:10.1007/978-3-319-18827-0_19 |
| [20] | Giering, R.; Kaminski, T., Recipes for adjoint code construction, ACM Trans. Math. Softw., 24, 4, 437-474 (1998) · Zbl 0934.65027 · doi:10.1145/293686.293695 |
| [21] | Gratton, S.; Lawless, AS; Nichols, NK, Approximate Gauss-Newton methods for nonlinear least square problems, SIAM J. Optim., 18, 1, 106-132 (2007) · Zbl 1138.65046 · doi:10.1137/050624935 |
| [22] | Gunther, S., Gauger, N.R., Schroder, J.B.: A non-intrusive parallel-in-time approach for simultaneous optimization with unsteady PDEs. arXiv:1801.06356v2 [math.OC] 28 Feb (2018) · Zbl 1428.35641 |
| [23] | Gurol, S.; Weaver, AT; Moore, AM; Piacentini, A.; Arango, HG; Gratton, S., B-preconditioned minimization algorithms for variational data assimilation with the dual formulation, Q. J. R. Metereol. Soc., 140, 539-556 (2014) · doi:10.1002/qj.2150 |
| [24] | Lawless, AS; Gratton, S.; Nichols, NK, On the convergence of incremental 4D-Var using non tangent linear models, Q. J. R. Meteorol. Soc., 131, 459-476 (2005) · doi:10.1256/qj.04.20 |
| [25] | Le Dimet, FX; Talagrand, O., Variational algorithms for analysis and assimilation of meteorological observations: theoretical aspects, Tellus, 38A, 97-110 (1986) · doi:10.1111/j.1600-0870.1986.tb00459.x |
| [26] | Levenberg, K., A method for the solution of certain non-linear problems in least squares, Q. Appl. Math., 2, 2, 164-168 (1944) · Zbl 0063.03501 · doi:10.1090/qam/10666 |
| [27] | Liao, Q.; Willcox, K., A domain decomposition approach for uncertainty analysis, SIAM J. Sci. Comput., 37, 1, A103-A133 (2015) · Zbl 1327.35464 · doi:10.1137/140980508 |
| [28] | Liu, DC; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Program., 45, 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116 |
| [29] | Liu, J.; Wang, Z., Efficient time domain decomposition algorithms for parabolic PDE-constrained optimization problems, Comput. Math. Appl., 75, 6, 2115-2133 (2018) · Zbl 1409.65055 · doi:10.1016/j.camwa.2017.09.017 |
| [30] | Marquardt, DW, An algorithm for the least-squares estimation of nonlinear parameters, SIAM J. Appl. Math., 11, 2, 431-441 (1963) · Zbl 0112.10505 · doi:10.1137/0111030 |
| [31] | Miyoshi, T.: Computational challenges in big data assimilation with extreme-scale simulations, talk at BDEC workshop. Charleston, SC (2013) |
| [32] | Moore, AM; Arango, HG; Broquet, G.; Powell, BS; Weaver, AT; Zavala-Garay, J., The regional ocean modeling system (ROMS) 4-dimensional variational data assimilation systems: I-system overview and formulation, Prog. Oceanogr., 91, 34-49 (2011) · doi:10.1016/j.pocean.2011.05.004 |
| [33] | Moore, AM; Arango, HG; Broquet, G.; Edwards, CA; Veneziani, M.; Powell, BS; Foley, D.; Doyle, JD; Costa, D.; Robinson, P., The regional ocean modeling system (ROMS) 4-dimensional variational data assimilation systems: II performance and application to the California current system, Prog. Oceanogr., 91, 50-73 (2011) · doi:10.1016/j.pocean.2011.05.003 |
| [34] | Moore, AM; Arango, HG; Broquet, G.; Edwards, CA; Veneziani, M.; Powell, BS; Foley, D.; Doyle, JD; Costa, D.; Robinson, P., The regional ocean modeling system (ROMS) 4-dimensional variational data assimilation systems: III observation impact and observation sensitivity in the California current system, Prog. Oceanogr., 91, 74-94 (2011) · doi:10.1016/j.pocean.2011.05.005 |
| [35] | Moore, AM; Arango, HG; Di Lorenzo, E.; Cornuelle, BD; Miller, AJ; Neilson, DJ, A comprehensive ocean prediction and analysis system based on the tangent linear and adjoint of a regional ocean model, Ocean Model., 7, 227-258 (2004) · doi:10.1016/j.ocemod.2003.11.001 |
| [36] | Murli, A., D’Amore, L., Laccetti, G., Gregoretti, F., Oliva, G.: A multi-grained distributed implementation of the parallel block conjugate gradient algorithm. Concurr. Comput. Pract. Exp. 22(15), 2053-2072 (2010) |
| [37] | Navon, IM; De Villiers, R., The application of the Turkel-Zwas explicit large time-step scheme to a hemispheric barotropic model with constraint restoration, Mon. Weather Rev., 115, 5, 1036-1052 (1987) · doi:10.1175/1520-0493(1987)115<1036:TAOTTE>2.0.CO;2 |
| [38] | Navon, IM; Yu, J., Exshall: a Turkel-Zwas explicit large time-step FORTRAN program for solving the shallow-water equations in spherical coordinates, Comput. Geosci., 17, 9, 1311-1343 (1991) · doi:10.1016/0098-3004(91)90030-H |
| [39] | Nerger, L.; Hiller, W., Software for ensemble-based data assimilation systems: implementation strategies and scalability, Comput. Geosci., 55, 110-118 (2013) · doi:10.1016/j.cageo.2012.03.026 |
| [40] | Neta, B.; Giraldo, FX; Navon, IM, Analysis of the Turkel-Zwas scheme for the two-dimensional shallow water equations in spherical coordinates, J. Comput. Phys., 133, 1, 102-112 (1997) · Zbl 0883.76060 · doi:10.1006/jcph.1997.5657 |
| [41] | PDAF https://pdaf.awi.de |
| [42] | NEMO Web page www.nemo-ocean.eu |
| [43] | Nichols, NK; Lahoz, W.; Khattatov, B.; Menard, R., Mathematical concepts of data assimilation, Data Assimilation: Making Sense of Observations, 13-40 (2010), Cham: Springer, Cham · Zbl 1194.86002 · doi:10.1007/978-3-540-74703-1_2 |
| [44] | Nocedal, J.; Wright, SJ, Numerical Optimization (1999), Cham: Springer-Verlag, Cham · Zbl 0930.65067 · doi:10.1007/b98874 |
| [45] | Nocedal, J.; Byrd, RH; Lu, P.; Zhu, C., L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Softw., 23, 4, 550-560 (1997) · Zbl 0912.65057 · doi:10.1145/279232.279236 |
| [46] | Nvidia.: TESLA K20 GPU active accelerator. Board spec. (2012) Available http://www.nvidia.in/content/PDF/kepler/Tesla-K20-Active-BD-06499-001-v02.pdf |
| [47] | https://parallel-in-time.org/ |
| [48] | PCIsig, tecnology specifications at https://pcisig.com/specifications/pciexpress/ |
| [49] | Rao, V.; Sandu, A., A time-parallel approach to strong constraint four dimensional variational data assimilation, J. Comput. Phys., 313, 583-593 (2016) · Zbl 1349.62455 · doi:10.1016/j.jcp.2016.02.040 |
| [50] | ROMS Web page www.myroms.org |
| [51] | Shchepetkin, AF; McWilliams, JC, The regional oceanic modeling system (ROMS): a split-explicit, free-surface, topography-following-coordinate oceanic model, Ocean Model., 9, 347-404 (2005) · doi:10.1016/j.ocemod.2004.08.002 |
| [52] | St-Cyr, A.; Jablonowski, C.; Dennis, JM; Tufo, HM; Thomas, SJ, A comparison of two shallow water models with nonconforming adaptive grids, Mon. Weather Rev., 136, 1898-1922 (2008) · doi:10.1175/2007MWR2108.1 |
| [53] | Ulriq, S.: Generalized SQP methods with “Parareal” time-domain decomposition for time-dependent PDE-constrained optimization. In: Biegler, L.T., Ghattas, O., Heinkenschloss, M., Keyes, D., van Bloemen Waanders, B. (eds.) Real-Time PDE-Constrained Optimization. SIAM, Philadelphia (2017) |
| [54] | Arcucci R., Carracciuolo L., D’Amore L.: On the problem-decomposition of scalable 4D-Var Data Assimilation models, Proceedings of the 2015 International Conference on High Performance Computing and Simulation, HPCS 2015 pp. 589-594, 2 September 2015 Article number 7237097 13th International Conference on High Performance Computing and Simulation, HPCS 2015Amsterdam20 July 2015 through 24 July 2015 |
| [55] | D’Amore L., Marcellino L., Mele V., Romano D.: Deconvolution of 3D fluorescence microscopy images using graphics processing units, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Volume 7203 LNCS, Issue PART 1, pp. 690-699, 2012 9th International Conference on Parallel Processing and Applied Mathematics, PPAM 201111 September 2011 through 14 September 2011 |
| [56] | D’Amore L., Casaburi D., Galletti A., Marcellino., Murli A.: Integration of emerging computer technologies for an efficient image sequences analysis. Integ. Comput. Aided Eng. 18(4), 365-378, doi:10.3233/ICA-2011-0382 (2011) |
| [57] | Murli, A., Boccia, V., Carracciuolo, L., D’Amore, L., Laccetti, G., Lapegna, M.: Monitoring and migration of a PETSc-based parallel application for medical imaging in a grid computing PSE. IFIP International Federation for Information Processing, vol. 239, pp. 421-432 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
