Source-linked AI summary
D-RADI: A Low-rank ADI Algorithm for Solving Large-scale Discrete-time Algebraic Riccati Equations
Umair Zulfiqar
TL;DR
Large-scale DAREs lack a dedicated low-rank ADI solver despite often having numerically low-rank solutions. The paper introduces D-RADI with automatic shift generation and reports accurate, efficient solutions for large problems while matching MATLAB's idare on moderate-order problems.
Problem
Large-scale DAREs lack a dedicated low-rank ADI algorithm, although their solutions are typically numerically low-rank when m, p ≪ n.
Method
D-RADI is a recursive low-rank ADI solver that uses projection and automatic shift generation to proceed without user intervention.
Results
D-RADI matches MATLAB's idare on moderate-order DAREs and accurately solves large-scale DAREs, converging in 19 iterations in 24.4192 seconds and 12 iterations in 20.1618 seconds.
Takeaways & Limitations
D-RADI provides an efficient, accurate, and fully autonomous approach for solving large-scale DAREs that are infeasible for MATLAB's idare.
Takeaways & Limitations
The formulation assumes E and R are invertible, while R and Z are indefinite, and stabilizing solutions require E^-1Acl to be Schur stable.
Abstract
from arXiv · showhide
The low-rank alternating direction implicit (ADI) method is an efficient numerical technique for solving several types of large-scale matrix equations that admit low-rank solutions. The discrete-time algebraic Riccati equation (DARE) is an important matrix equation with applications in state estimation, controller design, and filter design. In the literature, the low-rank Cholesky factor ADI method for Stein equations has been used within Newton iterations to solve large-scale DAREs. However, no dedicated low-rank ADI solver is available for such DAREs. To address this gap, this paper presents a low-rank ADI solver for large-scale DAREs. We also propose an efficient approach to generate ADI shifts automatically, which makes the proposed solver fully autonomous for solving DAREs. The effectiveness of the proposed solver is compared with MATLAB's \texttt{idare} on a moderate-order problem. Efficiency and accuracy are further demonstrated on large-scale DAREs of order $10^6$. Numerical results confirm that the solver is efficient, accurate, and fully autonomous.
1. Introduction
The paper formulates the discrete-time algebraic Riccati equation and focuses on computing its stabilizing solution. When input and output dimensions are much smaller than the state dimension, the solution is typically numerically low-rank, enabling scalable low-rank methods.
- DARE formulation: The paper considers a discrete-time algebraic Riccati equation with matrix coefficients Q, E, A, B, C1, C2, R, and Z.The formulation assumes E and R are invertible, while R and Z are indefinite.
- Stabilizing solution: A stabilizing solution is defined by Schur stability of the associated closed-loop state matrix E^-1Acl.The state-feedback gain K and closed-loop matrix Acl are introduced before this stability condition.
- Problem focus: The paper focuses on computing the stabilizing solution to the DARE.
- Large-scale motivation: When m, p ≪ n, the DARE solution is typically numerically low-rank, enabling low-rank methods for large n where direct methods are prohibitively expensive.This is the computational motivation for developing a dedicated large-scale solver.
2. Main Work
The paper develops D-RADI, a recursive low-rank ADI solver for large-scale DAREs that combines projection, rational interpolation, and stabilizing pole placement. It also provides autonomous shift generation and an implementation based mainly on shifted linear solves and basic matrix operations.
- Solver formulation: D-RADI fills the gap of a dedicated low-rank ADI algorithm for DAREs, producing a low-rank approximation to the stabilizing solution.The method is presented as a discrete-time counterpart of RADI and differs from using Stein-equation ADI inside Newton iterations.
- Solver formulation: Low-rank ADI methods are Petrov–Galerkin projection-based recursive rational interpolation algorithms that interpolate at mirror images of ADI shifts.The projected matrix equation is solved implicitly through the recursively accumulated low-rank factors.
- Stability: The projected closed-loop poles lie within the unit circle, ensuring that the projected solution is stabilizing throughout the ADI iterations.This is the proposed solver’s pole-placement property.
- Stability: ADI shifts outside the unit circle, together with the theorem’s stated assumptions, yield a stabilizing solution to the projected DARE.The assumptions include observability of the relevant pair and invertibility of the matrices X^(i)_r.
- Relation to Stein equations: When B = 0, R = I, and C2 = 0, the DARE reduces to a Stein equation and D-RADI reduces to an existing low-rank ADI solver for Stein equations.The corresponding theorem also reduces to previously derived Stein-equation results.
- Algorithm: The recursive implementation requires one shifted linear solve per iteration, while the small projected blocks are obtained analytically.The main computational step can use the Sherman–Morrison–Woodbury formula.
- Automatic shift generation: D-RADI is a recursive interpolation-based model order reduction algorithm whose shift selection targets dominant poles of the current reduced model.The approach uses mirror images of reciprocals of dominant residual poles to approximate the original transfer function accurately.
- Automatic shift generation: D-RADI generates subsequent shifts autonomously from projected Ritz values and repeats the previous shift when all projected poles lie outside the unit circle.The process starts from an arbitrary shift and continues until the residual reaches a prescribed tolerance.
3. Numerical Results
D-RADI is evaluated against MATLAB’s idare on a moderate-order DARE and on two large-scale DAREs of order 10^6. The experiments report accurate approximations, with the large-scale cases converging in roughly 20–25 seconds.
- The moderate-order test uses a heat transfer model with 200×200 state-space matrices and compares D-RADI with MATLAB’s idare.
- D-RADI converged in the 43rd iteration for the moderate-order problem, and its normalized residual history was recorded.
- The 66 nonzero singular values of Q(idare) were compared with those of Q(d-radi), showing that D-RADI produces an accurate approximation.
- D-RADI converged in the 19th iteration in 24.4192 seconds for a large-scale DARE of order 10^6, producing an accurate approximation in under 25 seconds.
- D-RADI converged in the 12th iteration in 20.1618 seconds for another large-scale DARE of order 10^6, producing an accurate approximation in about 20 seconds.
4. Conclusion
The paper proposes D-RADI, a fully autonomous low-rank ADI solver for large-scale DAREs. It matches MATLAB’s idare on moderate problems and efficiently solves large-scale problems that idare cannot handle.
- D-RADI is a low-rank ADI algorithm for computing low-rank solutions of large-scale DAREs.It uses interpolatory structure and pole placement to maintain a stabilizing projected DARE solution during ADI iterations.
- Automatic shift generation makes D-RADI fully autonomous, beginning from an arbitrary shift and continuing until the residual reaches a prescribed tolerance.
- D-RADI matches MATLAB’s idare accuracy on moderate-order DAREs while efficiently solving large-scale DAREs infeasible for idare.
Appendix
The appendix proves that the constructed matrix solves the projected DARE and is stabilizing. The proof establishes invertibility, reduces the residual using the Woodbury identity, and verifies spectral stability.
- Invertibility: The proof first verifies invertibility of the matrices needed to define the candidate solution and its residual.The argument uses properties of Q^(i)_r, R + B^(i)_r, and S^(i)_r before applying the Woodbury identity.
- Residual verification: The DARE residual is expanded and reduced by substituting the stated identities and applying the Woodbury identity.The resulting expression contains the projected DARE residual, which vanishes by the assumed equation.
- Stability: The candidate is a stabilizing solution because the relevant closed-loop eigenvalues lie strictly inside the unit circle.The proof uses eigenvalues -1/α_j with |α_j| > 1 and concludes that the candidate is stabilizing.
- Residual verification: The cross-terms in the residual cancel after using the defining identities and symmetry of the relevant matrices.The proof explicitly concludes that both cross-terms in the expanded residual vanish.
- Residual verification: The remaining middle matrix is simplified through the assumed identities and direct multiplication, yielding the required residual relation.The derivation substitutes the resulting expression and uses M^(0) = I_pm before completing the proof.