×

Nonlinear parallel-in-time Schur complement solvers for ordinary differential equations. (English) Zbl 1458.65075

Summary: In this work, we propose a parallel-in-time solver for linear and nonlinear ordinary differential equations. The approach is based on an efficient multilevel solver of the Schur complement related to a multilevel time partition. For linear problems, the scheme leads to a fast direct method. Next, two different strategies for solving nonlinear ODEs are proposed. First, we consider a Newton method over the global nonlinear ODE, using the multilevel Schur complement solver at every nonlinear iteration. Second, we state the global nonlinear problem in terms of the nonlinear Schur complement (at an arbitrary level), and perform nonlinear iterations over it. Numerical experiments show that the proposed schemes are weakly scalable, i.e., we can efficiently exploit increasing computational resources to solve for more time steps the same problem.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
65Y05 Parallel numerical computation

Software:

PARAEXP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Lions, J.; Maday, Y.; Turinici, A., A parareal in time discretization of pdes, Acad. Sci. Paris, 332, 661-668, (2001) · Zbl 0984.65085
[2] Emmett, M.; Minion, M. J., Toward an efficient parallel in time method for partial differential equations, Comm. App. Math. and Comp. Sci., 7, 105-132, (2012) · Zbl 1248.65106
[3] Gander, M. J., 50 years of time parallel time integration, (Multiple Shooting and Time Domain Decomposition, (2015), Springer) · Zbl 1337.65127
[4] Christlieb, A. J.; Macdonald, C. B.; Ong, B. W., Parallel high-order integrators, SIAM J. Sci. Comput., 32, 818-835, (2010) · Zbl 1211.65089
[5] Gander, M. J.; Güttel, S., Paraexp: A parallel integrator for linear initial-value problems, SIAM J. Sci. Comput., 35, C123-C142, (2013) · Zbl 1266.65123
[6] Falgout, R.; Friedhoff, S.; Kolev, T.; MacLachlan, S.; Schroder, J., Parallel time integration with multigrid, SIAM J. Sci. Comput., 36, C635-C661, (2014) · Zbl 1310.65115
[7] Badia, S.; Olm, M., Space-time balancing domain decomposition, SIAM J. Sci. Comput., 39, C194-C213, (2017) · Zbl 1365.65217
[8] Bellen, A.; Zennaro, M., Parallel algorithms for initial-value problems for difference and differential equations, J. Comput. Appl. Math., 25, 341-350, (1989) · Zbl 0675.65134
[9] Mandel, J.; Sousedík, B.; Dohrmann, C., Multispace and multilevel bddc, Computing, 83, 55-85, (2008) · Zbl 1163.65091
[10] Tu, X., Three-level BDDC in three dimensions, SIAM J. Sci. Comput., 29, 1759-1780, (2007) · Zbl 1163.65094
[11] Dohrmann, C. R., A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25, 246-258, (2003) · Zbl 1038.65039
[12] Badia, S.; Martí n, A. F.; Principe, J., Implementation and scalability analysis of balancing domain decomposition methods, Arch. Comput. Methods Eng., 20, 239-262, (2013) · Zbl 1354.65261
[13] Badia, S.; Martí n, A. F.; Principe, J., Multilevel balancing domain decomposition at extreme scales, SIAM J. Sci. Comput., C22-C52, (2016) · Zbl 1334.65217
[14] Cai, X.-C.; Keyes, D. E., Nonlinearly preconditioned inexact Newton algorithms, SIAM J. Sci. Comput., 24, 183-200, (2002) · Zbl 1015.65058
[15] Klawonn, A.; Lanser, M.; Rheinbach, O., Nonlinear FETI-DP and BDDC methods, SIAM J. Sci. Comput., 36, A737-A765, (2014) · Zbl 1296.65178
[16] Badia, S.; Martí n, A. F.; Principe, J., A highly scalable parallel implementation of balancing domain decomposition by constraints, SIAM J. Sci. Comput., 36, C190-C218, (2014)
[17] Badia, S.; Martí n, A. F.; Principe, J., On the scalability of inexact balancing domain decomposition by constraints with overlapped coarse/fine corrections, Parallel Comput., 50, 1-24, (2015)
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.