zbMATH — the first resource for mathematics

Parallel algorithms for algebraic Riccati equations. (English) Zbl 0763.93036
Algebraic Riccati equations (AREs) arise naturally in control design problems. Their importance has led to a good deal of research concerning their efficient numerical solution. The authors of the paper under consideration offer a parallel algorithm for solving the generalized ARE \[ A^ T XE+E^ T XA-E^ T XWXE+Q=0, \] where the matrices \(A\), \(E\), \(W\), and \(Q\) are all \(n\times n\), and the unknown \(X\) is also \(n\times n\). The given solution method is based on the matrix sign function algorithm. This is chosen primarily for its ease of parallelization. Three variations of the algorithm are given. The first uses pivoting in the matrix factorizations required; the second uses orthogonal transformations to put the matrix system into a tridiagonal form, which is then solved; and the third uses an updating strategy. The authors discuss implementation of the variations on a hypercube machine with distributed memory. They offer computational results, including speedups and efficiencies, for the resulting computer program on an Intel iPSC/d5 hypercube. Comparisons with sequential computations on a VAX 11/780 are also given. All parallel algorithms turn out to run faster than a standard scalar program when \(40\leq n\leq 100\), with the variation that uses pivoting performing best.
Reviewer: K.Cooper

93C15 Control/observation systems governed by ordinary differential equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
93-04 Software, source code, etc. for problems pertaining to systems and control theory
Full Text: DOI
[1] ARNOLD W. F., Proceedings of the Institute of Electrical and Electronics Engineers 72 pp 1746– (1984)
[2] DOI: 10.1109/CDC.1984.272049
[3] DOI: 10.1137/0708061 · Zbl 0222.65039
[4] DOI: 10.1137/0708060 · Zbl 0222.65038
[5] BUNSE-GERSTNER A., SIAM Conference on Control in the 90s (1989)
[6] BYERS , R. , 1983 , Hamiltonian and symplectic algorithms for the algebraic Ricatti equation . Ph.D. thesis , Cornell University ; 1989, Solving algebraic and discrete Riccati equations by nonsymmetric Jacobi iteration. SIAM Conference on Control in the 90s, San Francisco .
[7] DOI: 10.1007/BF02551818 · Zbl 0675.65032
[8] DONGARRA J. J., LINPACK Users’ Guide (1979)
[9] DOI: 10.1145/63047
[10] GARDINER , J. D. , 1988 , Iterative and parallel algorithms for the solution of algebraic Riccati equations . Ph.D. thesis , University of California , Santa Barbara .
[11] DOI: 10.1080/00207178608933634 · Zbl 0598.15012
[12] DOI: 10.1145/63047.63118
[13] HEATH , M. T. (editor), 1986 , Hypercube Multiprocessors 1986 ( Philadelphia SIAM ); 1987 Hypercube Multiprocessors 1987 (Philadelphia SIAM ). · Zbl 0654.68013
[14] DOI: 10.1109/MC.1987.1663563 · Zbl 05332241
[15] DOI: 10.1137/0612020 · Zbl 0725.65048
[16] DOI: 10.1016/0167-6911(89)90027-3 · Zbl 0685.93058
[17] DOI: 10.1109/TAC.1972.1099983 · Zbl 0262.93043
[18] DOI: 10.1080/00207178008922858 · Zbl 0439.49011
[19] DOI: 10.1109/TAC.1979.1102178 · Zbl 0424.65013
[20] DOI: 10.1016/0005-1098(77)90017-6 · Zbl 0359.49001
[21] DOI: 10.1109/TAC.1980.1102434 · Zbl 0456.49010
[22] DOI: 10.1080/00207178008922881 · Zbl 0463.93050
[23] DOI: 10.1137/0902010 · Zbl 0463.65024
[24] WILEY P., I.E.E.E. Spectrum 24 pp 46– (1987)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.