On parallel methods for boundary value ODEs. (English) Zbl 0723.65061
The article is concerned with parallel numerical methods for systems of two-point boundary value problems. In comparison with most other literature on this subject, it is remarkable that the stability of the presented parallel algorithms is studied in more detail.
With Newton’s method for nonlinear problems in mind, the analysis is restricted to linear boundary value problems. For the highly parallelizable standard multiple shooting algorithm, the stability problems occurring for boundary value problems are removed by a least- square-type variant, which is stable and has almost the same parallel complexity as the standard algorithm, but involves a worse condition number.
For stiff problems, another variant of the multiple shooting algorithm is proposed, where (stable) boundary value problems are solved “locally” instead of (unstable) initial value problems.
With Newton’s method for nonlinear problems in mind, the analysis is restricted to linear boundary value problems. For the highly parallelizable standard multiple shooting algorithm, the stability problems occurring for boundary value problems are removed by a least- square-type variant, which is stable and has almost the same parallel complexity as the standard algorithm, but involves a worse condition number.
For stiff problems, another variant of the multiple shooting algorithm is proposed, where (stable) boundary value problems are solved “locally” instead of (unstable) initial value problems.
Reviewer: M.Plum (Köln)
MSC:
| 65L10 | Numerical solution of boundary value problems involving ordinary differential equations |
| 65Y05 | Parallel numerical computation |
| 65L20 | Stability and convergence of numerical methods for ordinary differential equations |
| 34B05 | Linear boundary value problems for ordinary differential equations |
| 34E13 | Multiple scale methods for ordinary differential equations |
Keywords:
systems; stability; parallel algorithms; Newton’s method; multiple shooting algorithm; parallel complexity; condition number; stiff problemsSoftware:
COLSYSReferences:
| [1] | U. Ascher, J. Christiansen, R. D. Russell: ”Collocation software for boundary value ODEs”, Trans. Math. Software7 (1981), 209–222. · Zbl 0455.65067 · doi:10.1145/355945.355950 |
| [2] | U. Ascher, S. Jacobs: ”On collocation implementation for singularly perturbed two-point problems”, SIAM J. Scient. Stat. Comput.10 (1989), 533–549. · Zbl 0685.65076 · doi:10.1137/0910034 |
| [3] | U. Ascher, R. M. M. Mattheij: ”General framework, stability and error analysis for numerical stiff boundary value problems”, Numer. Math.54 (1988), 355–372. · Zbl 0666.65056 · doi:10.1007/BF01396767 |
| [4] | U. Ascher, R. M. M. Mattheij, R. D. Russell: ”Numerical solution of boundary value problems for ordinary differential equations”, Prentice-Hall (1988). · Zbl 0671.65063 |
| [5] | S. D. Conte: ”The numerical solution of linear boundary value problems”, SIAM Review8 (1966). 309–321. · Zbl 0168.14101 · doi:10.1137/1008063 |
| [6] | L. Dieci, M. R. Osborne, R. D. Russell: ”A Riccati transformation method for solving boundary value problems, I: theoretical aspects”, SIAM J. Numer. Anal.25, (1988), 1055–1074. · Zbl 0664.65074 · doi:10.1137/0725061 |
| [7] | T. N. Gambill, R. D. Skeel: ”Logarithmic reduction of the wrapping effect with application to ordinary differential equations”, SIAM J. Numer. Anal.25, (1988), 153–162. · Zbl 0638.65068 · doi:10.1137/0725012 |
| [8] | C. W. Gear: ”The potential for parallelism in ordinary differential equations”, Tech. Rep. 86-1246, Computer Science Dept. University of Illinois, Urbana (1988). · Zbl 0675.65068 |
| [9] | C. W. Gear: ”Massive parallelism across the method in ODEs”, Tech. Rep. 88-1442, Computer Science Dept. University of Illinois, Urbana (1988). · Zbl 0798.65075 |
| [10] | S. K. Godunov: ”Numerical solution of boundary value problems for systems of linear ordinary differential equations”, Usp. Mat. Nauk16 (1961), 171–174. |
| [11] | N. A. Haskell: ”The dispersion of surface waves in multilayered media”, Bull. Seism. Soc. Am.43 (1953), 17–34. |
| [12] | D. Heller: ”Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems”, SIAM J. Numer. Anal.13 (1976), 484–496. · Zbl 0347.65019 · doi:10.1137/0713042 |
| [13] | D. Heller: ”Direct and iterative methods for block tridiagonal linear systems”, PhD Thesis, Dept. Computer Science, CMU 1977. |
| [14] | F. de Hoog, R. M. M. Mattheij: ”On dichotomy and well-conditioning in BVP”, SIAM J. Numer. Anal.24 (1987), 89–105. · Zbl 0629.65084 · doi:10.1137/0724008 |
| [15] | S. L. Johnsson: ”Solving tridiagonal systems on ensemble architectures”, SIAM J. Scient. Stat. Comput.8 (1987), 354–392. · Zbl 0624.65021 · doi:10.1137/0908040 |
| [16] | R. N. Kapur, J. C. Browne: ”Techniques for solving block tridiagonal systems on reconfigurable array computers”, SIAM J. Scient. Stat. Comput.5 (1984), 701–719. · Zbl 0576.65018 · doi:10.1137/0905050 |
| [17] | R. M. Karp, V. Ramachandran: ”A survey of parallel algorithms for shared-memory machines”, Tech. Rep. UCB/CSD 88/408, UC Berkeley, 1988. · Zbl 0900.68267 |
| [18] | H. B. Keller: ”Numerical methods for two-point boundary value problems”, Blaisdell, 1968. · Zbl 0172.19503 |
| [19] | H.-O. Kreiss, N. K. Nichols, D. L. Brown: ”Numerical methods for stiff two-point boundary value problems”, SIAM J. Num. Anal.23 (1986), 325–368. · Zbl 0608.65049 · doi:10.1137/0723023 |
| [20] | M. Lentini: ”Parallel solution of special large block tridiagonal systems: TPBVP”, Manuscript, 1989. |
| [21] | M. Lentini: ”The potential for parallel algorithms in ordinary differential equations: boundary value problems”, Tech. Rep. 5/58, Lab. Nacional de Computacao Cientifica-LNCC, Rio de Janeiro, 1988. |
| [22] | M. Lentini, M. R. Osborne, R. D. Russell: ”The close relationships between methods for solving two-point boundary value problems”, SIAM J. Numer. Anal.21 (1984). · Zbl 0575.65080 |
| [23] | R. M. M. Mattheij: ”Decoupling and stability of algirithms for boundary value problems”, SIAM Review (1985), 1–44. · Zbl 0642.65064 |
| [24] | J. Nievergelt: ”Parallel methods for integrating ordinary differential equations”, Comm. ACM7 (1964), 731–733. · Zbl 0134.32804 · doi:10.1145/355588.365137 |
| [25] | J. M. Ortega, R. G. Voight: ”Solution of partial differential equations on vector and parallel computers”, SIAM Rev.27 (1985), 149–240. · Zbl 0644.65075 · doi:10.1137/1027055 |
| [26] | M. R. Osborne: ”On shooting methods for boundary value problems”, J. Math. Anal. Appl.27 (1969), 417–433. · Zbl 0177.20402 · doi:10.1016/0022-247X(69)90059-6 |
| [27] | B. A. Schmitt: ”An algebraic approximation to the matrix exponential in singularly perturbed boundary value problems”, SIAM J. Numer. Anal.27, (1990), 51–66. · Zbl 0689.65056 · doi:10.1137/0727004 |
| [28] | S. J. Wright: ”Stable parallel algorithms for two-point boundary value problems”, Preprint MCS-P178-0990, Argonne Nat. Lab. 1990. |
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.
