CS Paper Radar

Parallel Broyden Methods for Efficiently Evaluating Nonlinear State Space Models

Ian Christopher Tanoh, Scott W. Linderman

cs.LG math.NA ·submitted 2026-11-10 03:48 UTC · v1
top venuetheory

Abstract

Nonlinear state space models are typically evaluated sequentially, limiting their ability to exploit modern parallel hardware. Recent work has shown that state space models can be evaluated in parallel by reformulating evaluation as a root-finding problem, which can be solved with a parallel form of Newton's method. However, exact Newton methods require expensive multiplication of dense Jacobian matrices, and quasi-Newton methods based on diagonal approximations, while more scalable, are often slow to converge because they neglect interactions across state dimensions. We introduce a novel quasi-Newton approach based on Broyden's method, which captures coupling terms with diagonal-plus-low-rank approximations to blocks of the Jacobian. We construct the approximations from trajectory secants, avoiding automatic differentiation while retaining the favorable scaling of diagonal approximations and remaining compatible with parallel scan through rank compression. We prove finite-step recovery of the exact trajectory under the compressed scan, and show that convergence is tracked by the compression error and by the block approximation error along the current trajectory error, rather than in spectral norm. Empirically, we show that our method is advantageous when interactions are approximately low rank or when Jacobian evaluation is expensive: on low-rank RNNs, parallel MCMC algorithms, and denoising diffusion models, it converges in fewer iterations than other quasi-Newton methods and is the fastest parallel method when Jacobian evaluation is expensive or state dimensions are large.

Comment
Accepted at NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling

cs.LG cs.AI ·2026-09-28 ·Mónika Farsang, Ramin Hasani, Daniela Rus, Radu Grosu
similarity 0.64
Abstract

State space models (SSMs) achieve efficient sequence processing because their affine state updates are closed under composition and can therefore be evaluated with an associative parallel scan. Nonlinear recurrent models can provide richer, state-dependent dynamics, but generally lose this compositional structure: parallel evaluation then requires iterative methods that repeatedly linearize and scan the recurrence. We ask, what state-dependent nonlinear dynamics can be designed to remain exactly composable? We answer by introducing RiccatiSSM, a nonlinear SSM, in which each state dimension follows an input-conditioned Riccati differential equation. Its quadratic state dependence makes the local Jacobian explicitly state-dependent, while its exact per-step flow under piecewise-constant inputs is a Möbius transformation. Since Möbius maps are closed under composition and compose through $2\times 2$ matrix multiplication, the complete nonlinear state trajectory can be evaluated exactly with a single associative parallel scan, without iterative linearization. We further derive a constrained parameterization that ensures bounded, contractive dynamics, and avoids poles in the fractional-linear state update. Across long-sequence classification, regression, and forecasting tasks, RiccatiSSM achieves competitive predictive performance while reducing runtime by $22{-}33\%$ compared to the nonlinear LrcSSM under matched architectures. These results demonstrate that state-dependent nonlinear dynamics can retain exact composability and be evaluated efficiently within a single parallel scan.

0.23

Low-rank corrections to a shared reference Jacobian for GPU-parallel AC $N\!-\!1$ contingency analysis

eess.SY cs.DCmath.NA ·2026-11-02 ·Marc Hunkemöller, Nico Westerbeck, Joost van Dijk, Lars Schewe, Dirk Witthaut
similarity 0.60
Abstract · Submitted to IEEE Transactions on Power Systems. 10 pages, 5 figures, 1 table

Contingency analysis repeatedly solves the power-flow equations under many single-element outages, an increasingly demanding workload as operating margins tighten and renewable variability grows. Graphics processing units (GPUs) are attractive for this task, but a change in topology alters the sparsity pattern of the Jacobian, preventing the uniform batched factorization on which efficient GPU solvers rely. This paper presents a GPU-parallel Newton--Raphson solver for $N\!-\!1$ contingency analysis that separates the change in operating state from the change in topology. A single reference Jacobian is inverted once and reused across all contingencies. Each topology change is expressed as a low-rank Woodbury correction, while the residual state-dependent perturbation is handled by an inner iterative solve, a truncated Neumann series or the biconjugate gradient stabilized method. We analyze the spectral radius and condition number of the resulting iteration matrices and show that the reference Jacobian is an effective preconditioner. On transmission-scale benchmarks, the method attains per-topology solve times competitive with an optimized 80-core central processing unit baseline, with the low-rank correction accounting for approximately 1--2\% of the workload. This makes GPU-parallel $N\!-\!1$ contingency analysis feasible at transmission scale without per-topology refactorization.

0.33

Parallel Policy-Gradient Methods for Parameter Optimization of Nonlinear Feedback Controllers

eess.SY math.OC ·2026-09-12 ·An Nguyen, Leilei Cui
similarity 0.59
Abstract

Structured feedback controllers provide rigorous stability guarantees, but often require manual parameter tuning to achieve good closed-loop performance. Policy-gradient methods offer a systematic approach to parameter optimization; however, conventional gradient evaluation requires sequential forward state rollout and backward costate propagation. This letter develops a time-parallel policy-gradient framework for discrete-time nonlinear control-affine systems. We derive the policy-gradient expression where the state and costate rollouts required for policy-gradient evaluation are formulated as residual-minimization problems and solved using Gauss-Newton (GN) iterations with parallel associative scans. For closed-loop systems that are globally asymptotically stable and locally exponentially stable, we show that the residual-minimization problems satisfy a local Polyak-Lojasiewicz (PL) inequality and that the GN iterates converge locally at a quadratic rate. Moreover, the PL constant, the size of the convergence neighborhood, and the quadratic convergence bound are independent of the rollout horizon T. We also prove that, for any finite horizon T, the state solver recovers the exact trajectory from any initialization in at most T iterations. Finally, an inertia-wheel pendulum example with interconnection and damping assignment passivity-based control (IDA-PBC) demonstrates improved closed-loop performance and the computational benefits of the proposed parallel policy-gradient framework.

0.19

Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

cs.LG stat.MLmath.NAmath.OC+1 ·2026-09-11 ·Xinchen Du, Elizaveta Rebrova, Michał Dereziński, Sen Na
theory similarity 0.59
Abstract · 52 pages, 3 figures, 4 tables

We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.

0.34

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.57
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

Online adaptive non-intrusive model reduction via manifold interpolation and subspace updates: application to FSI convergence acceleration

cs.CE math.NA ·2026-09-15 ·Azzeddine Tiba, Florian de Vuyst, Iraj Mortazavi
similarity 0.56
Abstract

We introduce a novel online adaptive non-intrusive reduced-order modeling strategy for parameterized dynamical systems involving parameter and time-dependent reduced bases. The proposed framework is based on a unified Grassmann manifold formulation combining three key components: interpolation of local reduced subspaces for unseen parameters, geodesic online subspace updates driven by incoming high-fidelity snapshots, and a latent-space regression strategy relying on Grassmann-distance weighting and Procrustes alignment to consistently aggregate predictions from multiple local models. The adaptive reduced-order model is embedded in a partitioned fluid-structure interaction framework, where it predicts fluid interface forces to provide accurate initial guesses for the nonlinear coupling iterations, thus achieving computational speedups with no loss of accuracy. The reduced basis and the regression operators are adapted independently during the simulation and without requiring the storage of high-dimensional streaming data, preserving computational efficiency while substantially improving predictive capabilities. Numerical results on reference FSI test cases demonstrate superior accuracy with respect to static and global reduced-order models, leading to a significant reduction in the number of fixed-point iterations required for convergence. The proposed framework offers a flexible and fully non-intrusive approach for the efficient simulation of nonlinear parameter-dependent multiphysics problems.

0.23

Tensor-Train Compressed Separable PINNs: A Curvature-Aware Optimization Framework for Parametric PDEs in High Dimensions

cs.LG math.OCmath.NA ·2026-09-28 ·Denis Korolev, Martin Eigel
similarity 0.56
Abstract

In this work, we develop a second-order optimization framework for physics-informed neural networks (PINNs) applied to high-dimensional parametric partial differential equations (PDEs). The framework is built on the Gauss--Newton pullback metric, which provides an operator-informed notion of curvature in parameter space and connects the method to the broader family of natural gradient schemes. We show that, for coordinate-separable neural architectures and linear differential operators (or linearized operators in the nonlinear case) admitting a finite separable representation, the residual Jacobian inherits a structured separable factorization. This yields an exact compressed formulation of the Gauss--Newton step in a reduced space, without assembling the full residual Jacobian on the exponentially large tensor-product collocation grid. The dimension of the reduced space (the effective compressed dimension) is determined by the local collocation grid sizes, the separable operator structure, and the contraction pattern of the architecture, thereby avoiding dependence on the full tensor-product grid size and replacing dense linear algebra in parameter space by a substantially smaller structured problem. Within our framework, we investigate canonical polyadic and tensor-train parametrizations and derive their full algebraic characterization relevant to the Gauss--Newton method, including the structure of the residual Jacobian, the resulting compressed system, and its effective compressed dimension. Numerical experiments on high-dimensional PDEs, including parametric problems, demonstrate the high efficiency of the proposed compressed Gauss--Newton method, which achieves substantially lower errors than tensor-compressed first-order baselines with orders of magnitude fewer iterations and only a fraction of the computing time.

0.47

Block-Sparse Gauss-Newton Optimization of Finite Basis Physics-Informed Neural Networks: Sparse Automatic Differentiation Approach

cs.LG math.NA ·2026-11-09 ·Denis Korolev, Adrian Hill, Jeeeun Lee
similarity 0.56
Abstract

In this work, we develop an efficient Gauss-Newton optimization approach for finite basis physics-informed neural networks (FBPINNs). The key ingredient is the overlapping domain decomposition architecture of FBPINNs, which localizes the influence of each subnetwork and induces block sparsity in both the residual Jacobian and the corresponding Gauss-Newton matrix. We characterize this structure and exploit it through sparse automatic differentiation, using graph coloring to partition structurally orthogonal Jacobian columns or rows. This reduces differentiation costs and memory requirements while preserving all structurally nonzero derivative information. The resulting compressed Jacobian representations allow us to assemble the Gauss-Newton system directly in block-sparse form, enabling the use of sparse direct solvers and preconditioned iterative methods. In this way, the otherwise expensive second-order optimization problem is reduced to scalable sparse linear algebra. We demonstrate the approach on multiscale PDEs, where accurate approximation requires rich neural network parametrizations and large numbers of collocation points. Numerical experiments show that our block-sparse Gauss-Newton method attains high accuracy and substantially accelerates optimization relative to first-order baselines while remaining computationally tractable for large problem sizes.

0.05