CS Paper Radar

A New Generalized Low-Rank Cholesky Factor ADI Algorithm for Large-Scale Stein Equations

Umair Zulfiqar

eess.SY math.NA ·submitted 2026-08-23 13:27 UTC · v1
unusual

Abstract

The low-rank alternating direction implicit (ADI) method is an efficient solver for large-scale Stein equations with low-rank solutions. This paper shows that, as in the continuous-time Lyapunov equation case, the low-rank Cholesky factor ADI (LRCF-ADI) method for Stein equations implicitly performs $\mathcal{H}_2$-pseudo-optimal model order reduction for discrete-time systems. This observation leads to an automatic shift-generation strategy, allowing LRCF-ADI to select subsequent shifts without user intervention. The standard LRCF-ADI method requires shifts outside the unit circle. We generalize the method to allow shifts anywhere in the complex plane, including on the unit circle. This extension enables numerical integration for frequency-limited Stein equations by interpolating the integrand at points on the unit circle. It also enables non-intrusive, data-driven balanced truncation and frequency-limited balanced truncation using experimentally measurable transfer function samples on the unit circle, without requiring access to a state-space realization. Numerical results for large-scale models demonstrate the effectiveness of the proposed methods as low-rank Stein equation solvers and data-driven model order reduction methods.

Closest papers

Nearest neighbours by meaning across the whole index.

D-RADI: A Low-rank ADI Algorithm for Solving Large-scale Discrete-time Algebraic Riccati Equations

eess.SY math.NA ·2026-08-29 ·Umair Zulfiqar
similarity 0.68
Abstract

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.

0.13

A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations

eess.SY math.NA ·2026-09-18 ·Umair Zulfiqar
similarity 0.55
Abstract

Discrete-time non-symmetric algebraic Riccati equations (DTNAREs) arise in game-theoretic computations of Nash equilibria. Solving such equations at large scale is often computationally prohibitive. This paper develops a numerical approach for large-scale DTNAREs whose solutions are low rank. A low-rank alternating direction implicit (ADI) method is introduced that recursively constructs a low-rank stabilizing solution without explicitly solving any projected DTNARE. Through the pole-placement property of the low-rank ADI iteration, the method ensures that the implicitly solved projected DTNARE always admits a stabilizing solution. An automatic shift-generation strategy is also developed for the ADI iterations. Once an initial shift is provided, the algorithm computes the low-rank solution without further user intervention. Numerical experiments on DTNAREs with dimensions between \(10^6\) and \(10^7\) demonstrate the accuracy and efficiency of the method. The results confirm that the proposed low-rank ADI algorithm is an effective solver for large-scale DTNAREs that would otherwise be computationally prohibitive.

0.07

Symbolic Direct Construction of Augmented Systems for Levenberg-Marquardt Power Flow

eess.SY cs.PFmath.NA ·2026-10-25 ·Tianshi Cheng, Venkata Dinavahi
theory similarity 0.49
Abstract · 8pages, 1 figure

Levenberg-Marquardt power flow (LMPF) addresses ill-conditioned equations and provides least-squares stationary points for infeasible operating requests. Conventional implementations form damped normal equations, where J^T J introduces fill, squares the spectral condition number of the undamped part, and adds sparse-product cost. We propose an augmented LMPF formulation with a symbolic-permutation-based Jacobian operator that fills the augmented blocks directly. We prove that the matrix is symmetric quasi-definite for positive damping, enabling fixed-order, pivot-free QDLDL factorization. This property also motivates the solver choice: KLU value-only refactorization can reuse an unsuitable pivot order, forcing fresh full factorizations on difficult LMPF trajectories. We further introduce one-probe adaptive trust-region initialization for the radius and damping. Direct assembly is 7.5-11.9x faster than the fastest coordinate-list path and 18.0-58.8x faster than cached normal-equation sparse-product formation; QDLDL reduces numerical refactorization and triangular-solve time by up to 3.40x on identical matrices. Adaptive initialization solves flat-started RTE cases in 19-25 factorizations, 7.5-11.6x faster than reproduced three-step LM. On case2383wp, our 84-iteration run performs 84 factorizations and 168 resolves in 237 ms, versus published times of 200.780-441.72 s with fewer outer iterations, corresponding to speedups of 847-1860x. These results require complete factorization and resolve accounting and reveal initialization and legacy-parameter effects. DC-initialized NR exhibits fast quadratic convergence throughout every tested solvable loading range, motivating clearer, reproducible definitions of ill-conditioned power-flow benchmarks.

0.22

$H_2$-optimal model order reduction using hyperbolic geometry

eess.SY math.NA ·2026-10-12 ·Andrea Angino, Tamás Dózsa, Matthias Voigt
benchmark similarity 0.46
Abstract

We revisit the problem of approximating a linear time-invariant LTI model by a reduced-order model (ROM) in an $H_2$-optimal sense. A widely used method for computing such ROMs is the iterative rational Krylov algorithm (IRKA). However, in practice, the stability of the resulting ROM is not generally guaranteed. In this work, we develop a novel framework that can be used to obtain $H_2$-optimal models of single-input single-output LTI systems while enforcing stability of the ROM. We use Malmquist-Takenaka orthogonal expansions in the corresponding $H_2$-spaces and their connection to hyperbolic geometry to develop an equilibrium function. We show that the poles of an $H_2$-optimal ROM transfer function are defined by the zeros of this equilibrium function. The resulting nonlinear root-finding problem is solved using a Newton-type method formulated on the products of Poincaré disk manifolds, where updates are performed along hyperbolic geodesics ensuring that the stability constraint is satisfied at every iteration. We present numerical experiments on benchmark systems for both discrete- and continuous-time LTI MOR problems, including examples where IRKA produces unstable reduced models while the proposed method preserves stability throughout the iteration.

0.42

An Analytical Review of Model Order Reduction Methodologies of Converter-Dominated Power Systems for Stability Studies

eess.SY ·2026-10-02 ·Goran Grdenić, Marco Fraccaro, Josipa-Pina Milišić
similarity 0.45
Abstract · 53 pages, 4 figures

The rapid integration of renewable energy sources is transforming modern electric power systems into converter-dominated networks characterized by complex multi-timescale dynamics and new stability interactions over a wide frequency range. Accurate analysis of these phenomena requires high-fidelity models of transmission networks and power electronic converters, which often result in large-scale differential-algebraic systems with significant computational burden. This paper provides an analytical review of model order reduction techniques for converter-rich power systems, with particular emphasis on the key equations employed in the reduction process. Advantages and limitations of commonly used strategies, including timescale-based singular perturbation, projection-based, operator-based, data-driven, and machine-learning based methods, are discussed. The synthesis highlights key challenges related to harmonic interactions and multi-frequency dynamics, and outlines directions for the development of computationally efficient yet dynamically accurate reduced-order models for future power systems.

0.29

Norm-optimal model order reduction in reproducing kernel Hilbert spaces

cs.LG math.NAeess.SY ·2026-10-20 ·Tamás Dózsa, Andrea Angino, Rolf Krause, Matthias Voigt
theory similarity 0.45
Abstract · 92 pages, 7 figures

We consider the problem of model order reduction (MOR) in reproducing kernel Hilbert spaces (RKHSs). We prove generalizations of well-known necessary interpolatory conditions for norm-optimal reduced-order models, originally stated for rational functions in $H_2$ Hardy-Hilbert spaces. We construct an alternative to the iterative rational Krylov (IRKA) algorithm for RKHSs with differentiable kernels to obtain norm-optimal reduced-order models. Then, we introduce generalized Malmquist-Takenaka (GMT) functions that can be used to define orthonormal bases in an arbitrary RKHS. Using GMT functions, we propose unitary transformations between separable RKHSs. This allows us to extend our optimality conditions and subsequent algorithms to MOR problems posed in RKHSs with non-differentiable kernels. The potential and versatility of the proposed MOR framework is demonstrated in several numerical experiments. We perform norm-optimal MOR on various machine learning models such as support vector machines and deep ReLU networks. In addition, we show how the proposed MOR framework can be used to solve seemingly unrelated problems. In particular, we provide an example for fitting high degree polynomials to data and also obtain a FEM-like method for solving partial differential equations (PDEs) with an optimal kernel basis.

0.33

Stable Rational Approximation of PDE Transfer Functions with $H_\infty$ Error Bounds

eess.SY math.AP ·2026-10-06 ·Aleksandr Talitckii, Matthew M. Peet
unusual similarity 0.44
Abstract

Transfer functions of Partial Differential Equations (PDEs) are irrational and difficult to obtain. Unlike for rational transfer functions, only a few methods are available for the control and analysis of irrational transfer functions. Thus, for robust analysis and control of PDEs, we need to use a rational approximation of the transfer function, preferably with provable $H_\infty$ error bounds. In this paper, we extend Krylov subspace model reduction to infinite-dimensional systems modeled by Partial Integral Equations (PIEs) -- an equivalent representation of PDEs. First, we propose a state transformation of the PIE system that allows us to compute a controllability matrix. Then, to obtain a rational approximation, we project the PIE states onto the vector space spanned by the truncated controllability matrix. Next, we show that sufficient conditions for exponential stability and well-posedness of the PIE system guarantee the exponential stability of the reduced-order system and provide constructive finite-frequency $H_\infty$ error bounds. Finally, we provide four illustrative numerical examples to demonstrate the performance of the proposed method.

0.25

The Snapping Phenomenon and Boundary Enforcement in Model Reduction: Mechanisms and Mitigation

cs.CE ·2026-10-15 ·Charbel Farhat, Yihong Zhu, Faisal As'ad, Tommaso Taddei
similarity 0.44
Abstract · 29 pages, 13 figures

Projection-based model order reduction mitigates the computational cost of high-fidelity parametric simulations but can suffer from the "snapping phenomenon", whereby a projection-based reduced-order model (PROM) rigidly latches onto a training snapshot, impairing parametric interpolation. Standard methods also struggle to enforce parameter-dependent boundary conditions without costly constraints or penalty schemes. This work proposes a tripartite taxonomy of snapping, distinguishing intrinsic, extrinsic, and numerical mechanisms. Focusing on intrinsic and numerical snapping, we introduce a unified framework based on a parameter-dependent shift vector. By embedding spatial transport into the state ansatz, the method enforces boundary conditions exactly, restores continuous parametric sensitivity, and eliminates snapshot latching in affine and regression-augmented PROMs without increasing online complexity. We establish the framework's mathematical foundations in the linear regime, showing how it overcomes test-space orthogonality blind spots. In nonlinear computational fluid dynamics, we identify the roles of boundary conditions, mesh grading, and discrete equation scaling in numerical snapping. We also show that formulation-toggling is an unreliable heuristic that can compromise near-field accuracy. Finally, we develop a field-theoretic realization using a spatially varying shift vector governed by a scaled Laplace equation. The approach is validated on structural and aerodynamic benchmarks, including viscous flow around a NACA airfoil and a three-dimensional NASA Common Research Model.

0.22