Preconditioned linear solves for parametric model order reduction

ABSTRACT

The main computational cost of algorithms for computing reduced-order models of parametric dynamical systems is in solving sequences of very large and sparse linear systems of equations, which are predominantly dependent on slowly varying parameter values. We focus on efficiently solving these linear systems, specifically those arising in a set of algorithms for reducing linear dynamical systems with the parameters linearly embedded in the system matrices. We propose the use of the block variant of the problem-dependent underlying iterative method because often, all right hand sides are available together. Since Sparse Approximate Inverse (SPAI) preconditioner is a general preconditioner that can be naturally parallelized, we propose its use. Our most novel contribution is a technique to cheaply update the SPAI preconditioner, while solving parametrically changing linear systems. We support our proposed theory by numerical experiments where-in two different models are reduced by a commonly used parametric model order reduction algorithm called RPMOR. Experimentally, we demonstrate that using a block variant of the underlying iterative solver saves nearly 95% of the computation time over the non-block version. Further, and more importantly, block GCRO with SPAI update saves around 60% of the time over block GCRO with SPAI.

KEYWORDS:

• Parametric model order reduction
• parametrically dependent linear systems
• iterative methods
• SPAI preconditioner
• preconditioner updates

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 34C20
• 65F10

Acknowledgments

Thanks to the anonymous reviewers that helped us greatly improve the quality of this manuscript. We would also like to thank Prof. Qin (Tim) Sheng (Editor-in-Chief, International Journal of Computer Mathematics) for his tremendous support during the whole reviewing process.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 From here onwards, we represent a set of parameters as a set of expansion points.

2 Often, they work well for linear systems arising from certain problem classes [2,7,11], for example, discretization of PDEs in two dimensions.

3 Here, we use right preconditioning, i.e. the preconditioner is applied to the right of the linear system matrix. Similar analysis can be done with left preconditioning, i.e. with the preconditioner on the left of the linear system matrix.

4 We look at the first equation because the matrix change happens here only, which is the case that requires computation of a new preconditioner. In the other equations of (12(12) $\begin{array}{r}\begin{array}{l}\mathrm{Z}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{t}\mathrm{h}-\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{M}\mathrm{o}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}(h=0)\\ \mathcal{A}\left(i\right)x^{\left(i\right)}\left(1\right)=B,\\ \mathrm{F}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}-\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{M}\mathrm{o}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}(h=1)\\ \mathcal{A}\left(i\right)\left[x^{\left(i\right)}\left(2\right)\cdots x^{\left(i\right)}\left(\right(w+1)+1)\right]=\left[A_1{x}^{\left(i\right)}\left(1\right)\cdots A_{w+1}{x}^{\left(i\right)}\left(1\right)\right],\\ \mathrm{S}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}-\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{M}\mathrm{o}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}(h=2)\\ \mathcal{A}\left(i\right)\left[x^{\left(i\right)}\left(\right(w+1)+2)\cdots x^{\left(i\right)}\left(2\right(w+1)+1)\right]=A_1\left[x^{\left(i\right)}\left(2\right)\cdots x^{\left(i\right)}\left(\right(w+1)+1)\right],\\ ⋮\\ \mathcal{A}\left(i\right)\left[x^{\left(i\right)}(w+1)(w+1)+2)\cdots x^{\left(i\right)}((w+2)(w+1)+1)\right]=A_{w+1}\left[x^{\left(i\right)}\left(2\right)\cdots x^{\left(i\right)}\left(\right(w+1)+1)\right],\end{array}\end{array}$(12) ), the matrix remains the same and only the right-hand side changes. Thus, the preconditioner corresponding to the first equation is ideal.

5 As mentioned after (18(18) $\underset{Q_2}{min}\parallel \mathcal{A}\left(1\right)-\mathcal{A}\left(2\right)Q_2{\parallel }_f^2.$(18) ), we do not explicitly form the preconditioner by multiplying two matrices. Rather, the preconditioner is applied via a matrix-vector product.

6 Average values of $\parallel \mathcal{A}\left(1\right)-\mathcal{A}\left(3\right)\parallel /\parallel \mathcal{A}\left(1\right)\parallel$ for RPMOR applied to Micro-Gyroscope Model and Electro-Chemistry Model are $2.11\times {10}^{-09}$ and $1.77\times {10}^{-05}$, respectively. Also, average values of $\parallel \mathcal{A}\left(2\right)-\mathcal{A}\left(3\right)\parallel /\parallel \mathcal{A}\left(2\right)\parallel$ for the two respective models are $1.07\times {10}^{-09}$ and $7.66\times {10}^{-06}$, respectively.

7 For example, the average change in the frequency variable $s_1^i$, with the change in i for both Micro-Gyroscope and Electro-Chemistry models, is of the order 1. The maximum order of magnitude of the elements in the dynamical system sub-matrices for both these models is ${10}^{09}$.

8 All our linear system matrices are ill-conditioned as well; condition number of the order ${10}^{12}$.

9 0.016142 seconds for spMM with 6 right-hand sides and 0.012798 seconds for spMV.

10 The underlying linear solver, GCRO or block GCRO, does not affect this.

11 This is more general than computing the the error between the original system output and the reduced system output since for the latter, input range is also required.

Additional information

Funding

Further, the second author would like to duly acknowledge the support from MATRICS Scheme of DST-SERB, India (MTR/2017/001023).