A single LU~factorization approach to model reduction for linear system families with a quadratic matrix pencil
Abstract
To solve a family of large linear systems where the system matrix depends on the family parameter quadratically, we propose a new solution approach. Our method employs the derivatives of solutions with respect to the parameter. It turns out that the accumulated solution derivatives of increasing order, evaluated at a single specially chosen parameter value, provide successively better approximations to solution subspaces for the whole linear system family. We show that the derivatives can be computed by a recurrence, involving, at each step, solving a linear system with the same matrix. Constructing an orthonormal basis for the subspace spanned by the derivatives then leads to an efficient solver where just a single (sparse) LU factorization (or a single preconditioner setup in an iterative scheme) suffices to solve the whole linear system family. We call the new method ODB (orthonormal derivative basis method). As shown in numerical tests, compared to conventional solution methods, the ODB method allows to drastically reduce computational costs.
Related
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
- PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming
- Improved deterministic integer factorization by quadratic-image sieving
- Infinite families of pairs of real quadratic fields whose class numbers are divisible by a given integer
- CUDA-MPQS: A GPU-Resident Self-Initializing Quadratic Sieve, and the Factorization of RSA-155
BibTeX
@misc{botchev2026single,
title = {{A single LU~factorization approach to model reduction for linear system families with a quadratic matrix pencil}},
author = {Mikhail A. Botchev and Leonid Knizhnerman and Nikolai L. Zamarashkin and Dmitry A. Zheltkov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14902},
eprint = {2610.14902},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14902},
}
RIS
TY - UNPB
TI - A single LU~factorization approach to model reduction for linear system families with a quadratic matrix pencil
AU - Mikhail A. Botchev
AU - Leonid Knizhnerman
AU - Nikolai L. Zamarashkin
AU - Dmitry A. Zheltkov
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14902
UR - https://arxiv.org/abs/2610.14902
AB - To solve a family of large linear systems where the system matrix depends on the family parameter quadratically, we propose a new solution approach. Our method employs the derivatives of solutions with respect to the parameter. It turns out that the accumulated solution derivatives of increasing order, evaluated at a single specially chosen parameter value, provide successively better approximations to solution subspaces for the whole linear system family. We show that the derivatives can be computed by a recurrence, involving, at each step, solving a linear system with the same matrix. Constructing an orthonormal basis for the subspace spanned by the derivatives then leads to an efficient solver where just a single (sparse) LU factorization (or a single preconditioner setup in an iterative scheme) suffices to solve the whole linear system family. We call the new method ODB (orthonormal derivative basis method). As shown in numerical tests, compared to conventional solution methods, the ODB method allows to drastically reduce computational costs.
ER -