Sie können Operatoren mit Ihrer Suchanfrage kombinieren, um diese noch präziser einzugrenzen. Klicken Sie auf den Suchoperator, um eine Erklärung seiner Funktionsweise anzuzeigen.
Findet Dokumente, in denen beide Begriffe in beliebiger Reihenfolge innerhalb von maximal n Worten zueinander stehen. Empfehlung: Wählen Sie zwischen 15 und 30 als maximale Wortanzahl (z.B. NEAR(hybrid, antrieb, 20)).
Findet Dokumente, in denen der Begriff in Wortvarianten vorkommt, wobei diese VOR, HINTER oder VOR und HINTER dem Suchbegriff anschließen können (z.B., leichtbau*, *leichtbau, *leichtbau*).
Dieser Artikel geht auf die Herausforderungen und Lösungen für die Annäherung von Lösungen an parametrisierte lineare Systeme mit mehreren Parametern ein. Der Schwerpunkt liegt auf der HOPGD-Methode von Tschebyschew in Kombination mit einer spärlichen Netzabtastung, die einen neuartigen und effizienten Ansatz bietet. Der Text untersucht die Generierung von Schnappschusslösungen mittels Tschebyschew-Interpolation und die Konstruktion von Modellen reduzierter Ordnung durch Tensorzersetzung. Es wird auch die Anwendung dieser Methoden auf Probleme der Parameterschätzung diskutiert. Der Artikel schließt mit numerischen Simulationen, die die Effektivität der vorgeschlagenen Methoden demonstrieren und wertvolle Erkenntnisse für Fachleute auf diesem Gebiet liefern.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
We consider approximating solutions to parameterized linear systems of the form \(A(\mu _1,\mu _2) x(\mu _1,\mu _2) = b\), where \((\mu _1, \mu _2) \in \mathbb {R}^2\). Here the matrix \(A(\mu _1,\mu _2) \in \mathbb {R}^{n \times n}\) is nonsingular, large, and sparse and depends nonlinearly on the parameters \(\mu _1\) and \(\mu _2\). Specifically, the system arises from a discretization of a partial differential equation and \(x(\mu _1,\mu _2) \in \mathbb {R}^n\), \(b \in \mathbb {R}^n\). The treatment of linear systems with nonlinear dependence on a single parameter has been well-studied, and robust methods combining companion linearization, Krylov subspace iterative methods, and Chebyshev interpolation have enabled fast solution for multiple values of a single parameter at the cost of a single iteration. For systems depending nonlinearly on multiple parameters, the computation becomes much more challenging. This work overcomes those additional challenges by combining robust strategies for treating a single parameter with tensor-base approaches; i.e., combining companion linearization, the Krylov subspace method preconditioned bi-conjugate gradient (BiCG), and a decomposition of a tensor matrix of precomputed solutions, called snapshots. This produces a reduced order model of \(x(\mu _1,\mu _2)\), and this model can be evaluated inexpensively for many values of the parameters. An interpolation of the model is used to produce approximations on the entire parameter space. In addition this method can be used to solve a parameter estimation problem. This approach allows us to achieve similar computational savings as for the one-parameter case; we can solve for many parameter pairs at the cost of many fewer applications of an efficient iterative method. The technique is presented for dependence on two parameters, but the strategy can be extended to more parameters using the same theoretical approach. Numerical examples of a parameterized Helmholtz equation show the competitiveness of our approach. The simulations are reproducible, and the software is available online.
This work was supported by the Department of Mathematics, Royal Institute of Technology (KTH), SeRC Swedish e-Science Research Center, Lindstedtsvägen 25, Stockholm, Sweden.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
We are interested in approximating solutions to linear systems of the form
for many different values of the parameters \(\mu _1, \mu _2\). Here \(A(\mu _1,\mu _2) \in \mathbb {R}^{n \times n}\) is a large and sparse nonsingular matrix with a nonlinear dependence on \(\mu _1 \in [a_1,b_1] \subset \mathbb {R}\) and \(\mu _2 \in [a_2,b_2] \subset \mathbb {R}\) and \(x(\mu _1,\mu _2) \in \mathbb {R}^n\), \(b \in \mathbb {R}^n\). Further, the system matrix arises from a discretization of a parameterized partial differential equation (PDE) and can be expressed as the sum of products of matrices and functions, i.e.,
where \(n_f \ll n\) and \(f_1,\ldots ,f_{n_f}\) are nonlinear scalar functions in the parameters \(\mu _1\) and \(\mu _2\). This is usually referred to as split form.
The treatment of large-scale linear systems depending on a single parameter has been explored widely in the literature. Initially, this was for the case of linear dependence on the parameter (e.g., [21, 23, 41]). Strategies for treating nonlinear dependence on the parameter [14, 15, 26] were then built on top of the strategies for treating the case of linear dependence. What these works all have in common is that they allow for the evaluation of the solution for multiple values of the single parameter at the cost of a single iteration of a Krylov subspace method. This greatly reduces the costs, since the dominant costs (i.e., matrix–vector products and dot products) are independent from the number of evaluations of the solution for different parameter values. Our work represents the next step: how to derive an approach for systems depending on multiple parameters.
Anzeige
The goal of achieving similar savings when the system depends on more than one parameter, such as in (1.1), is much more challenging. We describe how to build on the work for single-parameter-dependent linear systems in order achieve this goal for the multi-parameter-dependent case. We combine the companion linearization-based Krylov subspace iteration employed in [14, 15, 26] for the single parameter case with a tensor decomposition to construct a reduced order model. This smaller model can be evaluated inexpensively to approximate the solution to (1.1) for many values of the parameters. Additionally, the model can be used to solve a parameter estimation problem, i.e., to simultaneously estimate \(\mu _1\) and \(\mu _2\) for a given solution vector where these parameters are not known. We describe our strategy in terms of dependence of (1.1) on two parameters, but the theory extends to more than two parameters.
More specifically, our proposed method is based on a decomposition of a tensor matrix of precomputed solutions to (1.1), called snapshots. In this way, building the reduced order model can be divided into two main parts:
1.
Generate the snapshots for many pairs \((\mu _1,\mu _2)\) efficiently using the technique from [15].
2.
Perform the tensor decomposition.
2 From one to more parameters
The transition from treating a system depending on a single parameter to one depending on multiple parameters presents an interesting challenge. The work in [14, 26] is based on generating a Taylor expansion of the system matrix with respect to a single parameter centered around some point. Generalizing this directly to the multiple-parameter case can at times not produce satisfactory results due to a tight radius of convergence. Instead, we find that building on the approach in [15] allows for the derivation of a more robust algorithm for treating (1.1). Generating a truncated Taylor expansion is equivalent to constructing a Hermite interpolation at a single point for a certain number of derivatives at that point. We can interpret the work in [15] as replacing Hermite interplation with Chebyshev interpolation on the interval of interest for the single parameter. This leads to a different companion linearization of the same problem, and one can evaluate for many values of parameters on the interval for the cost of a single preconditioned Krylov subspace iteration (in this case a BiCG-based iteration [20, 29]). Furthermore, Chebyshev interpolation comes with robust error estimates allowing for precise control of the interpolation error.
2.1 Reduced order model from snapshots
The strategy we propose to treat (1.1) is to construct a reduced order model for \(x(\mu _1,\mu _2)\) for which we generate snapshots (samples) varying one parameter at a time. This allows us to efficiently acquire the snapshots using the robust single-parameter algorithm proposed in [15]. There have been many prior works that rely on sampling; see, e.g., [7, 8, 31‐34]. In particular, solutions corresponding to each \((\mu _1,\mu _2)\) in the tensor matrix are obtained by solving the linear systems individually. Using Preconditioned Chebyshev BiCG [15] to obtain the snapshots allows for great flexibility in the selection of the set of snapshots included in the tensor, as the approximations are generated as one variable functions of \(\mu _1\) or of \(\mu _2\), i.e., with one parameter fixed. These functions are cheap to evaluate for different values of the parameter, and this method is described in Sect. 2.2.
Anzeige
The tensor matrix of precomputed snapshots used here has a particular structure, as we consider sampling on a structured, sparse grid in the parameter space. This is a way to overcome the so-called curse of dimensionality, since the number of snapshots to generate and store grows exponentially with the dimension when the sampling is performed on a conventional full grid. Note, this work deals only with tensors of order 3 in order to fully study the fundamental behavior of this method.
The decomposition is performed with a variant of the higher-order proper generalized decomposition1 (HOPGD), as proposed in [31]. The approach here has been adapted for this particular setting with fewer snapshots and, as in the standard implementation, results in a separated expression in \(\mu _1\) and \(\mu _2\). Once constructed, the decomposition is interpolated to approximate solutions to (1.1) corresponding to all parameters \((\mu _1,\mu _2) \in [a_1,b_1] \times [a_2,b_2]\).
In general, we cannot guarantee that the error in a tensor decomposition for a certain set of snapshots will reach a specified accuracy level. Further, it is not known a priori which sets of snapshots will lead to a successful decomposition, even with modest standards for the convergence2 [27]. Different selections of snapshots can lead to models that are more efficient to compute and more robust overall, but the optimal set is not known beforehand. Moreover, generating the snapshots is the dominating cost of building the reduced order model. In instances where the decomposition process fails to converge or yields an inadequate model, our proposed method provides an effective remedy. It facilitates the generation of a new set of snapshots within the same parameter space \([a_1, b_1] \times [a_2, b_2]\) with little extra computation. These snapshots can be used to construct a new reduced order model for the same parameter space in an identical way. This is the main contribution developed in this work; we refer to Sect. 4 for additional elaboration.
More precisely, an alternating directions, greedy algorithm is used to perform the decomposition, where the cost of each step of the method grows linearly with the number of unknowns n. The basis vectors for the decomposition are not known beforehand, similar to the established proper generalized decomposition (PGD), often used to create reduced order models of PDEs that are separated in the time and space variables. The method PGD has been used widely in the study of highly nonlinear PDEs [11‐13] and has been generalized to solve multiparametric problems; see, for instance, [5, 6].
Evaluating the resulting reduced order model is in general much more efficient than solving the systems individually for each choice of the parameters [31]. Reliable and accurate approximations are available for a variety of parameter choices, and parameter estimation can be performed in a similarly competitive way. Details regarding the construction of the reduced order model are found in Sect. 3, and the novel contribution is explained in detail in Sect. 4. Numerical simulations of a parameterized Helmholtz equation and a parameterized advection–diffusion equation are presented in Sects. 5 and 6, respectively. All experiments were carried out on a 2.3 GHz Dual-Core Intel Core i5 processor with 16 GB RAM, and the corresponding software can be found online.3
2.2 Generating snapshots with Preconditioned Chebyshev BiCG
Reduced order models based on sampling of snapshot solutions are typically constructed by generating many finite element approximations individually in an offline stage. We base our approach to obtain the snapshot solutions \(x(\mu _1,\mu _2)\) to (1.1) on an adapted version of the Preconditioned Chebyshev BiCG method for parameterized linear systems, originally proposed in [15]. Here, the unique solution to a companion linearization, formed from an arbitrarily accurate Chebyshev approximation using Chebfun [17], is generated in a preconditioned BiCG [20, 29] setting. Companion linearization is common in the study of nonlinear eigenvalue problems. The linearization used here was chosen because of its prior application to solving parameterized linear systems. Other choices may lead to competitive approaches, e.g., [39, 42, 44].
Two executions of this method generate all finite element solutions corresponding to the values of the parameters shown in Fig. 2. Specifically, one execution for all solutions on the line \(\mu _1 = \mu _1^*\) and one execution for all solutions on the line \(\mu _2 = \mu _2^*\) in the plane \([a_1, b_1] \times [a_2, b_2]\). In this way, we generate solutions fixed in one parameter. Moreover, the sampling represented here is sufficient to build a reliable reduced order model with the strategy presented in [31]. We briefly summarize this method as follows.
A Chebyshev approximation of \(A(\mu _1,\mu _2)\) for a fixed \(\mu _2^* \in \mathbb {R}\) is given by \(P(\mu _1)\), where
Here \(\tau _{\ell }\) is the degree \(\ell \) Chebyshev polynomial on \([-c_1,c_1]\) and \(P_{\ell }\in \mathbb {R}^{n \times n}\) are the corresponding interpolation coefficients. Note, \(c_l \in \mathbb {R}\) is chosen such that \([a_l,b_l] \subseteq [-c_l,c_l]\), for \(l=1,2\). A companion linearization based on the linear system
$$\begin{aligned} P (\mu _1) \hat{x} (\mu _1) = b \end{aligned}$$
(2.2)
with \(\hat{x}(\mu _1) = \hat{x}(\mu _1,\mu _2^*) \approx x(\mu _1,\mu _2^*)\), where \(x(\mu _1,\mu _2^*)\) is as in (1.1), and a fixed \(\mu _2^*\) has the form
$$\begin{aligned} \left( K - \mu _1 M \right) u(\mu _1) = c, \end{aligned}$$
(2.3)
where \(K, M \in \mathbb {R}^{d n \times d n}\) are coefficient matrices, independent of the parameter \(\mu _1\), \(c \in \mathbb {R}^{d n}\) is a constant vector, and the solution \(u(\mu _1)\) is unique. This linearization, inspired by the work [18] and studied fully in [15], relies on the well-known three-term recurrence of the Chebyshev polynomials.
Solutions to the systems in (2.3) are approximated with the Krylov subspace method bi-conjugate gradient for shifted systems [2, 22]. Specifically, we approximate an equivalent shifted system, preconditioned with \((K-\sigma M)^{-1}\), given by
$$\begin{aligned} & ( K - \mu _1 M )(K-\sigma M)^{-1} \hat{u}(\mu _1) = c \end{aligned}$$
where \(\hat{u}(\mu _1) = (K- \sigma M) u (\mu _1)\). The kth approximation comes from the Krylov subspace generated from the matrix \(M (K - \sigma M)^{-1}\) and the vector c, defined by
where \(\mathcal {K}_k = \mathcal {K}_k(M (K - \sigma M)^{-1},c)\). In particular, the method exploits the shift- and scaling- invariance properties of Krylov subspaces, and the preconditioner is applied efficiently based on the prior works [4, 28].
A Lanczos biorthogonalization process generates a basis matrix \(V_{k}\in \mathbb {R}^{d n \times k}\) for (2.5) and a tridiagonal matrix \(T_k\in \mathbb {R}^{k \times k}\) such that
holds, where \(\beta _k \in \mathbb {R}\), \(I_k\) is the identity matrix of dimension k, and \(e_k\) is the kth column of \(I_k\). Further, \(v_{k+1}\) is the \((k+1)\)th column in the basis matrix for \(\mathcal {K}_{k+1}\).
Approximations to (2.3) and, equivalently, approximations to (1.1), can be computed efficiently for \(\mu _1^i\), \(i=1,\ldots ,n_1\), as follows:
Here, \(\beta {:}{=}\left\Vert b\right\Vert \), where b is as in (1.1), and \(x_k(\mu _1,\mu _2^*)\) denotes the approximation to (1.1) from the Krylov subspace (2.5) of dimension k corresponding to \((\mu _1,\mu _2^*)\). Equivalently, \(x_k(\mu _1,\mu _2^*) \approx \hat{x}(\mu _1,\mu _2^*)\), where \(\hat{x}(\mu _1,\mu _2^*)\) is the solution to the system (2.2). Note, the subscript on the right-hand side of (2.6c) denotes the first n elements in the vector.
Since \(k \ll n\), solving the tridiagonal system in (2.6a) is not computationally demanding. As a result, once we build a sufficiently large Krylov subspace via one execution of the main algorithm, we have access to approximations \(x_k(\mu _1^i,\mu _2^*)\) for all \(\mu _1^i\) in the interval \([a_1,b_1]\). The process of approximating (1.1) for a fixed \(\mu _1^*\) and \(\mu _2^j\), for \(j=1,\ldots ,n_2\), is completely analogous to the above procedure and, thus, we have access to approximations \(x_k(\mu _1^*,\mu _2^j)\) for all \(\mu _2^j\) on the interval \([a_2,b_2]\), obtained in a similarly efficient way.
Remark 2.1
(Choice of target parameter) The use of shift-and-invert preconditioners with well-chosen \(\sigma \) generally result in fast convergence, i.e., a few iterations of the shifted BiCG algorithm. This is because \((K-\mu _1 M)(K-\sigma M)^{-1} \approx I\), for \(\mu _1 \approx \sigma \). Note, taking \(\sigma = \mu _1\) results in a breakdown of the method.
3 Sparse grid based HOPGD
Let \(X (\mu _1,\mu _2) \in \mathbb {R}^{n \times n_1 \times n_2}\) be a sparse, three-dimensional tensor of approximations to (1.1). These precomputed snapshots, generated by two executions of the preconditioned Krylov subspace method described in Sect. 2.2, correspond to the pairs of parameters \((\mu _1^i,\mu _2^*)\), \(i=1,\ldots ,n_1\), and \((\mu _1^*,\mu _2^j)\), \(j=1,\ldots ,n_2\). Here, \(\mu _1^i\) are in the interval \([a_1,b_1]\), \(\mu _2^j\) are in the interval \([a_2,b_2]\), and \(\mu _1^* \in [a_1,b_1]\), \(\mu _2^* \in [a_2,b_2]\) are fixed values. More precisely,
and the remaining entries of \(X(\mu _1,\mu _2)\) are zeros; see Fig. 1 for a visualization of a tensor of this form. Note, \(\hat{x}(\mu _1^i,\mu _2^*)=\hat{x} (\mu _1^i)\) are approximations to the linear systems \(A(\mu _1^i,\mu _2^*)x(\mu _1^i,\mu _2^*)=b\) and \(\tilde{x}(\mu _1^*,\mu _2^j)=\tilde{x}(\mu _2^j)\) approximate solutions to \(A(\mu _1^*,\mu _2^j)x(\mu _1^*,\mu _2^j)=b\). We refer to the set
as the nodes and \(\varvec{\mu } \subset [a_1,b_1] \times [a_2,b_2]\). The set of nodes corresponding to the tensor matrix \(X(\mu _1,\mu _2)\) in Fig. 1 are visualized in Fig. 2. This way of sampling in the parameter space is a way to mitigate the so-called curse of dimensionality in terms of the number of snapshots to generate and store.
Fig. 1
Example of tensor matrix \(X(\mu _1,\mu _2)\) consisting of 9 snapshot solutions (dots connected by vertical lines) and reduced order model \(X^m(\mu _1,\mu _2)\) of rank m as in (3.3), where \(\Phi _n^k \in \mathbb {R}^n\), \(\varvec{f_1^k}{:}{=}\begin{bmatrix} F_1^k(\mu _1^1),\ldots ,F_1^k(\mu _1^5)\end{bmatrix} \in \mathbb {R}^5\), \(\varvec{f_2^k}{:}{=}\begin{bmatrix}F_2^k(\mu _2^1),\ldots ,F_2^k(\mu _2^5) \end{bmatrix} \in \mathbb {R}^5\). Approximation is sum of rank-one tensors
Sampling on a sparse grid in the parameter space. Nodes (3.2) correspond to the 9 snapshot solutions in Fig. 1 with \(\mu _1 \in [a_1,b_1]\), \(\mu _2 \in [a_2,b_2]\), \(\mu _1^* = (a_1+b_1)/2\), \(\mu _2^* = (a_2 + b_2)/2\). All snapshots generated via two executions of Preconditioned Chebyshev BiCG
Sparse grid based higher order proper generalized decomposition (HOPGD) [31] is a method which generates a tensor \(X^m(\mu _1,\mu _2) \in \mathbb {R}^{n \times n_1 \times n_2}\) to approximate \(X(\mu _1,\mu _2)\). Specifically, the approximations are separated in the parameters \(\mu _1\) and \(\mu _2\) and, at each pair of parameters in (3.2), are of the form
are one variable scalar functions of the parameters \(\mu _1\) and \(\mu _2\), respectively. Here m is the rank of the approximation and \(F_{l}^k\), \(l=1,2\), are the unknown functions of the kth mode. In this way, the nonzero entries of the tensor \(X(\mu _1,\mu _2)\) are estimated by a linear combination involving products of lower-dimensional functions; see (3.5).
The decomposition in (3.3) generates only the evaluations of \(F_{l}^k\), and the reduced basis vectors for the approximation are not known a priori. Instead, these vectors are determined on-the-fly, in contrast to other methods based on the similar proper orthogonal decomposition [7, 12]. A visualization of this decomposition on a sparse tensor of snapshots appears in Fig. 1. The spacing of the nodes is equidistant in both the \(\mu _1\) and \(\mu _2\) directions, conventional for methods of this type.
We note the similarity between this method and the well-known higher-order singular value decomposition (HOSVD) [30]. Additionally, the reduced order model generated via the method sparse grid based HOPGD is of the same form as the established CANDECOMP/PARAFAC (CP) decomposition. Specifically, the approximations consists of a sum of rank-one tensors [27]. This is visualized in Fig. 1.
Efficient tensor decompositions have been the focus of several previous works. In [38], a Tucker-like approximation with was generated from an \(n \times n \times n\) array in linear time, and a randomized algorithm was successfully implemented in order to compute a low-rank Tucker decomposition in [25]. Moreover, in [16], a linear time version of a tensor adaptive cross approximation was presented. That method, which makes use of a rational approximation algorithm, is fundamentally different from the method we propose to use, based on solving sequences of least squares approximations.
The model as expressed in (3.3) can only be evaluated on the set of nodes (3.2) corresponding to the snapshots included in the tensor matrix (3.1). To access other approximations, interpolations of \(F_l^k\) will be required; see Sect. 3.2. The particular structure of the sampling incorporated here is very similar to that which is used in traditional sparse grid methods for PDEs [10]. Our approach differs fundamentally from these methods, which are based on an interpolation of high dimensional functions using a hierarchical basis. See [9] for a method in this style, where a reduced order model was constructed using hierarchical collocation to solve parametric problems.
Remark 3.1
(Evaluation of the model at a point in space) The approximation in (3.3) is expressed using vectors of length n as the examples that follow in Sect. 5 concern a parameterized PDE discretized on a spatial domain denoted by \(\Omega \). We are interested in the solutions to these PDEs for many values of the parameters \(\mu _1\) and \(\mu _2\). The approximation (3.3), expressed at a point in space, is denoted by
for a particular \((\mu _1,\mu _2)\in \varvec{\mu }\) (3.2), where \(x_0 \in \Omega \subset \mathbb {R}^d\) is a spatial parameter, d is the dimension, and \(\Phi ^k(x_0) \in \mathbb {R}\) is an entry of the vector \(\Phi _n^k \in \mathbb {R}^n\) in (3.3). Specifically, \(\Phi _n^k\) denotes \(\Phi ^k\) evaluated on \(\Omega _{dp}\), where \(\Omega _{dp} \subset \Omega \). As in (3.3), to evaluate the model in (3.5) for values of \(\mu _1\) and \(\mu _2\) outside of the set of nodes, interpolations must be performed.
3.1 Computation of the separated expression
Traditionally, tensor decomposition methods require sampling performed on full grids in the parameter space, requiring the computation and storage of many snapshot solutions. See [8, 32, 34] for HOPGD performed in this setting, as well as an example in Sect. 5.2. The tensor decomposition proposed in [31] is specifically designed for sparse tensors. In particular, the sampling is of the same form considered in Sect. 2.2 and shown in Figs. 1 and 2. This approach is more efficient, as it requires fewer snapshots and, as a result, the decomposition is performed in fewer computations. The method in [31], adapted to our particular setting, is briefly summarized here.
We seek an approximation to the mode-1 fibers, i.e., the nonzero vertical columns of \(X(\mu _1,\mu _2)\) described in (3.1), and this approximation should be separated in the parameters \(\mu _1 \in [a_1,b_1]\) and \(\mu _2 \in [a_2,b_2]\). The full parameter domain is defined by \(\mathcal {D} {:}{=}\Omega \times [a_1,b_1] \times [a_2,b_2]\), where \(\Omega \subset \mathbb {R}^d\). We express solutions as vectors of length n, i.e., as approximations to (1.1) evaluated at a particular node \((\mu _1,\mu _2)\); cf. (3.5), where solutions are expressed at a single point in the spatial domain. The approximations satisfy
for \((\mu _1,\mu _2) \in \varvec{\mu }\), where \(\varvec{\mu }\) is the set of nodes defined in (3.2), and are generated via an alternating directions strategy. Specifically, at each enrichment step m, all components \(\Phi _n^m \in \mathbb {R}^n\), \(F_1^m(\mu _1) \in \mathbb {R}\), and \(F_2^m(\mu _2)\in \mathbb {R}\) in (3.6c) are initialized and updated sequentially. The components are used to construct an \(L^2\) projection of \(X(\mu _1,\mu _2)\), which is then added to the approximation. The updates are done via a greedy algorithm, where all components are assumed fixed, except the one we seek to compute. The process is equivalent to the minimization problem described as follows. At step m, find \(X^m(\mu _1,\mu _2) \in V_m \subset L^2(\mathcal {D})\) as in (3.6) such that
\(\mathcal {D}\) is the full parameter domain, and \(V_m\) represents a set of test functions. Equivalently, using the weak formulation, we seek the solution \(X^m(\mu _1,\mu _2)\) to
Here \((\cdot ,\cdot )_{\mathcal {D}}\) denotes the integral of the scalar product over the domain \(\mathcal {D}\), and (3.8) can be written as
$$\begin{aligned} \left( w \Phi _n^m F_1^m F_2^m, \delta X \right) _{\mathcal {D}} = \left( w X(\mu _1,\mu _2) - wX^{m-1}(\mu _1,\mu _2), \delta X \right) _{\mathcal {D}}, \quad \forall \delta X \in V_m. \end{aligned}$$
(3.9)
We have simplified the notation in (3.9) with \(F_1^m {:}{=}F_1^m(\mu _1)\) and \(F_2^m {:}{=}F_2^m(\mu _2)\) for readability. The mth test function is given by \(\delta X {:}{=}\delta \Phi ^m F_1^m F_2^m + \Phi _n^m \delta F_1^m F_2^m + \Phi _n^m F_1^m \delta F_2^m\), though, in practice, approximations to (3.9) are computed successively via a least squares procedure until a fixed point is detected without the explicit use of test functions. The approximation (3.6c) is updated with the resulting components.
More concretely, let the initializations \(\Phi _n^{m}\), \(\varvec{f_1^m} {:}{=}\begin{bmatrix} F_1^{m}(\mu _1^1),\ldots ,F_1^m(\mu _1^{n_1}) \end{bmatrix}\in \mathbb {R}^{n_1}\), \(\varvec{f_2^m} {:}{=}\begin{bmatrix} F_2^{m}(\mu _2^1),\ldots ,F_2^m(\mu _2^{n_2}) \end{bmatrix}\in \mathbb {R}^{n_2}\) be given. We seek first an update of \(\Phi _n^{m_\text {old}}{:}{=}\Phi _n^{m}\), assuming \(F_1^{m_{\text {old}}} {:}{=}F_1^{m}\), \(F_2^{m_{\text {old}}} {:}{=}F_2^{m}\) are known function evaluations for all \((\mu _1,\mu _2) \in \varvec{\mu }\). We update \(\Phi _n^m\) as
Denote the vector obtained in (3.10) by \(\Phi _n^{m_{\text {new}}}\) and seek an update of \(F_1^{m_\text {old}}(\mu _1^i)\), assuming \(\Phi _n^m\), \(F_2^m(\mu _2^j)\) known, using
for \(i=1,\ldots ,n_1\). We denote the solutions found in (3.12) by \(F_1^{m_{\text {new}}}(\mu _1^i)\). Note, \(\Phi _n^{m_\text {new}}\) and \(F_2^{m_\text {old}}(\mu _2^j)\) are used in the computations in (3.12). The updates \(F_2^{m}(\mu _2^j)\) are computed as
for \(j=1,\ldots ,n_2\), which we denote by \(F_2^{m_\text {new}}(\mu _2^j)\), where \(\Phi _n^{m_\text {new}}\) and \(F_1^{m_{\text {new}}}(\mu _1^i)\) were used in the computations in (3.13). For a certain tolerance level \(\varepsilon _1\), if the relation
we have approached a fixed point. In this case, the approximation in (3.6c) is updated with the components \(\Phi _n^m\), \(F_1^m(\mu _1^i)\), and \(F_2^m(\mu _2^j)\). If the condition (3.14) is not met, we set \(\Phi _n^{m_{\text {old}}} {:}{=}\Phi _n^{m_{\text {new}}}\), \(F_1^{m_{\text {old}}} (\mu _1^i) {:}{=}F_1^{m_{\text {new}}}(\mu _1^i) \), \(F_2^{m_{\text {old}}}(\mu _2^j) {:}{=}F_2^{m_{\text {new}}}(\mu _2^j)\) and repeat the process described above. If
is met for a specified \(\varepsilon _2\) and all \((\mu _1,\mu _2) \in \varvec{\mu }\), the algorithm terminates. Otherwise, we seek \(\Phi _n^{m+1}\), \(F_1^{m+1}(\mu _1^i) \), \(F_2^{m+1}(\mu _2^j) \) using the same procedure, initialized with the most recent updates. This process is summarized in Algorithm 1.
In general, decompositions of many sets of snapshots can be performed to an acceptable accuracy level with \(m \ll n\), where the parameter m depends on the regularity of the exact solution [12]. Efficiency and robustness have been shown for the standard PGD method generated with a greedy algorithm like the one described here [13, 32, 37]. Note, the accuracy of the approximations here depends strongly on the quality of the separated functions in the model [31]. Additionally, the decomposition produced by the standard HOPGD method is optimal when the separation involves two parameters [34].
The reduced order model described here can be used to approximate solutions to (1.1) for many \((\mu _1, \mu _2)\) outside of the set of nodes. This is achieved through interpolating the one variable functions in (3.4). Consider also a solution vector \(x (\mu _1,\mu _2)\in \mathbb {R}^n\) to (1.1), where \((\mu _1,\mu _2)\) are unknown. The interpolation of \(X^m(\mu _1,\mu _2)\) can be used to estimate the parameters \(\mu _1\), \(\mu _2\) that produce this particular solution.
Remark 3.2
(Separated expression in more than two parameters) The reduced order model (3.3) is separated in the two parameters \(\mu _1\) and \(\mu _2\). In [31], models separated in as many as six parameters were constructed, where the sampling was performed on a sparse grid in the parameter space. The authors note this particular approach for the decomposition may not be optimal in the sense of finding the best approximation, though it is possible. Our proposed way of computing the snapshots could be generalized to a setting separated in s parameters. In this way, the procedure would fix \((s-1)\) parameters at a time and execute Chebyshev BiCG a total of s times.
Remark 3.3
(Comparison of HOPGD to similar methods) In [34], HOPGD was studied alongside the similar HOSVD method. The decompositions were separated in as many as six parameters, and the sampling was performed on a full grid in the parameter space. In general, HOPGD produced separable representations with fewer terms compared with HOSVD. In this way, the model constructed by HOPGD can be evaluated in a more efficient manner. Furthermore, the method HOPGD does not require the number of terms in the separated solution to be set a priori, as in a CP decomposition.
Algorithm 1
Chebyshev HOPGD with sparse grid sampling for parameterized linear systems
The tensor representation in (3.3) consists, in part, of one-dimensional functions \(F_1^k\) and \(F_2^k\), for \(k=1,\ldots ,m\). Note, we have only evaluations of these functions at \(\mu _1^i\), \(i=1,\ldots ,n_1\) and \(\mu _2^j\), \(j=1,\ldots ,n_2\), respectively, and no information about these functions outside of these points. In this way, we cannot approximate the solution to (1.1) for all \((\mu _1,\mu _2) \in [a_1,b_1] \times [a_2,b_2]\) using (3.3) as written.
We can use the evaluations \(F_1^k(\mu _1^i)\) and \(F_2^k(\mu _2^j)\) in (3.3) to compute an interpolation of these one-dimensional functions in a cheap way. In practice, any interpolation is possible and varying the type of interpolation does not contribute significantly to the overall error in the approximation. Thus, we make the following interpolation of the representation in (3.3):
where \(\varvec{F}_1^k\), \(\varvec{F}_2^k\) are spline interpolations of \(F_1^k\), \(F_2^k\) (3.4), respectively, and \(\varvec{X}^m(\mu _1,\mu _2): [a_1,b_1]\times [a_2,b_2]\rightarrow \mathbb {R}^n\). The interpolation in (3.17) can be evaluated to approximate (1.1) for other \((\mu _1, \mu _2) \in [a_1,b_1] \times [a_2,b_2]\) in a cheap way. This approximation to \(x(\mu _1, \mu _2)\) is denoted as
Note, simply interpolating several snapshots to estimate solutions to (1.1) for all \((\mu _1,\mu _2)\) in the parameter space is not a suitable approach, as the solutions tend to be extremely sensitive to the parameters [34].
To solve the parameter estimation problem for a given solution \(x(\mu _1,\mu _2) \in \mathbb {R}^n\) that depends on unknown parameters \((\mu _1,\mu _2)\), we use the Matlab routine fmincon. This routine uses the sequential quadratic programming algorithm [36] to find the pair of values \((\mu _1, \mu _2)\) in the parameter domain that minimizes the quantity
Simulations from a parameterized Helmholtz equation and a parameterized advection–diffusion equation appear in Sects. 5 and 6, respectively. In these experiments, an interpolation of a reduced order model is constructed to approximate the solutions to the parameterized PDEs.
Remark 3.4
(Offline and online stages) In practice, the fixed point method in Algorithm 1 can require many iterations until convergence, though the cost of each step scales linearly with the number of unknowns. Residual-based accelerators have been studied to reduce the number of these iterations [31]. This strategy, though outside the scope of this work, has shown to be beneficial in situations where the snapshots depended strongly on the parameters. Only one successful decomposition is required to construct (3.17). Thus, the offline stage of the method consists of generating the snapshots with Chebyshev BiCG and executing Algorithm 1.
Evaluating the reduced order model (3.17) requires only scalar and vector operations and, therefore, a variety of approximations to (1.1) can be obtained very quickly, even when the number of unknowns is large. We consider this part of the proposed method the online stage. In the experiment corresponding to Fig. 7, evaluating the reduced order model had simulation time 0.010601 CPU seconds. Generating the corresponding finite element solution with backslash in Matlab had simulation time 1.197930 CPU seconds.
Remark 3.5
(Sources of error) The approximations generated by Algorithm 1 contain error from the Chebyshev approximation, the iterative method Preconditioned Chebyshev BiCG, the low-rank approximation, as well as the interpolations in (3.17). The Chebyshev approximation, which is accurate to the level of machine precision, has a very small impact on the overall error, and Fig. 4 shows that the iterative method obtains relatively accurate approximations to the true solutions. In practice, the interpolations performed in (3.17) are done on smooth functions, as visualized in Fig. 5. The largest source of error from our proposed algorithm stems from the tensor decomposition, i.e., lines 1–17 in Algorithm 1. This can be seen, for example, in Fig. 6. Conventional equidistant nodes construct the reduced order model from a variety of solutions.
4 Novel contribution of our approach
Clearly, the most expensive operations in Algorithm 1 are the inner products of two vectors of dimension n, and, thus, the cost of each step in the tensor decomposition scales linearly with the number of unknowns in (1.1). However, the choice of nodes (3.2) has a very large influence on the overall expense of the decomposition. In particular, the sampling determines how many iterations are taken until a fixed point is found and how many modes m are included in the reduced order model. If too many snapshots are included in the tensor matrix, the decomposition can fail to converge within expected time constraints.
The choice of nodes can also determine the quality of the resulting model. Specifically, the decomposition considered in this work is sensitive to overfitting. When overfitting occurs, the snapshots are well approximated by the model, but approximations corresponding to pairs of \((\mu _1,\mu _2)\notin \varvec{\mu }\) are not acceptably accurate. Moreover, not including enough snapshots in the tensor matrix can be problematic. This scenario can result in high levels of error, as the model has not received sufficient information to capture the underlying structure of the solutions, a situation referred to as underfitting.
It is not known a priori which sets of snapshots will produce acceptable models, as such convergence theory does not currently exist. Thus, it is advantageous to have access to solutions corresponding to many different pairs of \((\mu _1,\mu _2)\), as the initial selection rarely leads to a robust and accurate model. The traditional approach of generating snapshots one-by-one by solving finite element systems can be exceptionally costly.
Our proposed method, which computes the snapshots as one-variable functions using Preconditioned Chebyshev BiCG, offers an effective means of generating a wide range of accurate snapshots by utilizing a precomputed Krylov basis matrix. Consequently, accurate models for parameterized linear systems of the form (1.1) can essentially be obtained by solving a tridiagonal system of dimension \(k \times k\) for each snapshot.
While the optimal set of snapshots is problem-dependent, our experience suggests that starting with a coarse selection of equally-spaced nodes and adding more until the overall error is reduced is a reasonable strategy. One must also take into account the storage demands related to the snapshots when the dimension n is very large.
5 Numerical simulations of a parameterized Helmholtz equation
We consider both a reduced order model for a parameterized Helmholtz equation and a parameter estimation problem for the solution to a parameterized Helmholtz equation. Such settings occur naturally, for example, in the study of geophysics; see [34, 40, 45]. These prior works were also based on a reduced order model, constructed using PGD. Similarly, the method PGD was used in the study of thermal process in [1], and a reduced basis method for solving parameterized PDEs was considered in [24].
In the simulations which follow, the matrices \(A_i\) arise from a finite element discretization, and b is the corresponding load vector. All matrices and vectors here were generated using the finite element software FEniCS [3]. The solutions to these discretized systems were approximated with a modified version of the Kryov subspace method Preconditioned Chebyshev BiCG [15], as described in Sect. 2.2. This strategy requires a linear solve with a matrix of dimension \(n \times n\) on each application of the preconditioner and of its adjoint. We have chosen to perform the linear solve by computing one LU decomposition per execution of the main algorithm, which is reused at each subsequent iteration accordingly. This can be avoided by considering the inexact version of Preconditioned Chebyshev BiCG, described in the original work.
This work proposes a novel improvement in generating snapshot solutions necessary for constructing models of this type. We choose to include three different examples in this section in order to fully capture the versatility of our strategy. Once the interpolation (3.17) has been constructed, evaluating the approximations for many values of the parameters \(\mu _1\) and \(\mu _2\) can be done in an efficient manner; see Remark 3.4. In the case of the tensor decomposition failing to converge sufficiently or the model lacking accuracy outside of the original snapshots, a new set of approximations can be generated with little extra work. From these solutions, a new decomposition can be attempted; see Sect. 4.
It is important to note that the sparse grid sampling strategy visualized in Fig. 1 is not always sufficient for approximating highly oscillatory problems, even if many nodes are selected. For this reason, we have included simulations corresponding to a full grid in Sect. 5.2. The adaptive refinement strategy proposed in [31] could also be considered for such problems, though it is not used here. Specifically, a repeated sparse grid sampling procedure similar to Fig. 1 could be employed in regions of the parameter space associated with high errors. Repeated executions of Preconditioned Chebyshev BiCG would offer an efficient way to generate snapshots in this context as well.
5.1 First simulation, snapshots sampled on a sparse grid
where \(\Omega \subset \mathbb {R}^2\) is as in Fig. 7, \(\mu _1 \in [1,2]\), \(\mu _2 \in [1,2]\), \(f(\mu _1,\mu _2 ) = 2 \pi ^2 + \cos (\mu _1) + \mu _1^4 + \sin (\mu _2) + \mu _2\), and \(h(x) = \sin (\pi x_1) \sin (\pi x_2)\). A discretization of (5.1) is of the form (1.1), where
We are interested in approximating u(x) in (5.1) for many different pairs of \((\mu _1,\mu _2)\) simultaneously.
The reduced order model \(\varvec{X}^m(\mu _1,\mu _2)\) is constructed as described in Algorithm 1. We can evaluate this model for \((\mu _1,\mu _2)\) outside of the nodes corresponding to the snapshot solutions. The particular 13 nodes considered in this simulation are plotted in the parameter space, shown in Fig. 3. Figure 4 displays the convergence of the two executions of Preconditioned Chebyshev BiCG required to generate the snapshots corresponding to the nodes in Fig. 3. Specifically, in Fig. 4a, we see faster convergence for approximations \(\hat{x}(\mu _1,\mu _2^*)\) where the value \(\mu _1\) is closer to the target parameter \(\sigma \) in (2.4); see Remark 2.1. Note, we consider \(\sigma =1.48\) to demonstrate the behavior of the method. An analogous result holds in Fig. 4b. We require the LU decompositions of 2 different matrices of dimension \(n \times n\) for this simulation.
In Fig. 5, we see the interpolations \(\varvec{F}_1^1(\mu _1)\) and \(\varvec{F}_2^1(\mu _2)\) as in (3.17) plotted along with the function evaluations \(F_1^1(\mu _1^i)\) and \(F_2^1(\mu _2^j)\) generated by Algorithm 1, where \(\mu _1^i\) and \(\mu _2^j\) are as in Fig. 3. Figure 6 shows the percent relative error for approximations to (5.1) for a variety of pairs \((\mu _1,\mu _2)\) different from the nodes plotted in Fig. 3. As in [32], we consider approximate solutions with percent relative error below \(6 \%\) reliable and approximations with percent relative error below \(1.5 \%\) accurate, where the error is computed by comparing the approximation to the solution obtained using backslash in Matlab. Figs. 7, 8, and 9 show both the exact finite element solution and the solution generated from (3.17) for the sake of comparison. Here we display these solutions for 3 pairs of \((\mu _1,\mu _2)\). These approximations all have percent relative error below \(1.5 \%\). A variety of solutions can be obtained from this reduced order model.
Fig. 3
Locations of 13 snapshots \((\mu _1^i,\mu _2^*)\) and \((\mu _1^*,\mu _2^j)\) used to construct \(X^m\) in (3.3) to approximate (5.1), sampling on a sparse grid in the parameter space
Convergence of Preconditioned Chebyshev BiCG for generating the snapshot solutions corresponding to the nodes in Fig. 3 with \(\sigma =1.48\). Simulation in Fig. 4a gives all solutions for \((\mu _1,\mu _2^*)\), \(\mu _1 \in [1,2]\), simulation in Fig. 4b gives all solutions for \((\mu _1^*,\mu _2)\), \(\mu _2 \in [1,2]\)
Function evaluations \(F_1^1(\mu _1^i)\) and \(F_2^1(\mu _2^j)\) produced by Algorithm 1 to approximate (5.1), plotted with corresponding interpolations \(\varvec{F}_1^1(\mu _1)\) and \(\varvec{F}_2^1(\mu _2)\) as in (3.17) with \(\mu _1^i\) and \(\mu _2^j\) as in Fig. 3
Percent relative error of \(x^m(\mu _1,\mu _2)\) (3.18) to approximate (5.1) for 400 equidistant pairs of \((\mu _1,\mu _2)\), \(m=14\), \(n= 112,995\). Here accurate: \(< 1.5 \%\), reliable: \(< 6 \%\). Note, same model in both figures
5.2 Second simulation, snapshots sampled on a full grid
To obtain an accurate model over the entire parameter space, we consider using HOPGD with sampling performed on a full grid. This is the approach taken in [8, 32] to approximate parametric PDEs. The snapshots are obtained using the Krylov subspace method described in Sect. 2.2, and the model is constructed in a way that is completely analogous to the method described in Sect. 3. As the decomposition is performed on a tensor matrix containing more snapshots, the method is more costly.
Specifically, we build a reduced order model to approximate the solution to the Helmholtz equation given by
where \(\Omega \subset \mathbb {R}^2\) is as in Fig. 11, \(\alpha (x) = x_2\), \(\mu _1 \in [1,2]\), \(\mu _2 \in [1,2]\), and \(f_1(\mu _1) = \cos (\mu _1) + \mu _1^3\), \(f_2(\mu _2) = \sin (\mu _2) + \mu _2^2\), \(h(x)=\sin (\pi x_1) \sin (\pi x_2)\). A discretization of (5.2) is of the form (1.1), where
and approximating u(x) in (5.3) for many different pairs of \((\mu _1,\mu _2)\) is of interest. We can still exploit the structure of the sampling when generating the snapshots by fixing one parameter and returning solutions as a one variable function of the other parameter. As in the simulations based on sampling on a sparse grid, if the decomposition fails to reach a certain accuracy level, or the model is inadequate due to overfitting or not enough data, a new set of snapshots can be generated with little extra computational effort. These solutions can be used to build a better model.
Figure 10a shows the locations of the nodes corresponding to 77 different snapshot solutions used to construct a reduced order model. These snapshots were generated via 7 executions of a modified form of Preconditioned Chebyshev BiCG, i.e., we consider 7 different fixed \(\mu _2^*\), equally spaced on \([a_2,b_2]\). This requires the LU decompositions of 7 different matrices of size \(n \times n\). Figure 10b shows the percent relative error of the interpolated approximation, analogous to (3.17) constructed using Algorithm 1, for 400 pairs of \((\mu _1,\mu _2) \in [1,2] \times [1,2]\), different from the nodes corresponding to the snapshot solutions. We note that the percent relative error of the approximation is below \(1 \%\) for all pairs \((\mu _1,\mu _2)\), indicating that the approximations are accurate. For the sake of comparison, Figs. 11, 12 and 13 show both the exact finite element solutions and corresponding reduced order model solutions for 3 pairs of \((\mu _1,\mu _2)\). In general, accurate solutions can be produced on a larger parameter space with sampling on a full grid. Furthermore, the model can produce a variety of solutions.
Fig. 10
Simulation for approximating (5.2). Here percent relative error \(< 1.5 \%\) (accurate), \(n=112693\), \(m=16\), sampling on a full grid
5.3 Third simulation, parameter estimation with snapshots sampled on a sparse grid
We consider now an application of our method to solve a parameter estimation problem. Similar methods have been constructed in the context of parameterized PDEs, for example, [33, 35, 40]. Our approach is analogous to the experiments performed in [33], where several reduced order models were constructed using the method sparse grid based HOPGD [31]. Consider the Helmholtz equation given by
where \(\Omega = [0,1] \times [0,1]\), \(\alpha (x) = x_1\), \(f_1(\mu _1) = \sin ^2 (\mu _1)\), \(f_2(\mu _2) = \cos ^2(\mu _2)\), \(\mu _1 \in [0,1]\), \(\mu _2 \in [0,1]\), and \(h(x)=\exp (-x_1 x_2)\). A discretization of (5.3) is of the form (1.1), where
We consider a parameter estimation problem, i.e., we have a solution to the discretized problem, where the parameters \((\mu _1,\mu _2)\) are unknown. In particular, the solution is obtained using backslash in Matlab.
Figure 14a–c together show a method similar to the one proposed in [33] for approximating this problem, performed by constructing 3 successive HOPGD models with sampling on sparse grids. This simulation executes a modified form of Preconditioned Chebyshev BiCG 6 times, requiring the LU factorizations of 6 different matrices of dimension \(n \times n\) to generate the 39 snapshot solutions used to create the 3 reduced order models. Once the models have been constructed, an interpolation is performed, followed by the minimization of (3.19). Table 1 shows the percent relative error in the estimated values of \(\mu _1\) and \(\mu _2\) for each run. Each execution of our strategy leads to a better estimation of the pair of parameters. As before, if the decomposition fails to reach a certain level of accuracy on a set of snapshots, or the model is lacking in robustness, a new set of approximations in the same parameter space can be generated with little extra computational effort. These solutions can be used in order to construct a better model.
Fig. 14
Parameter estimation for solution to (5.3), \(n=10024\)
Percent relative error for parameter estimation in \(\mu _1\) and \(\mu _2\) for solution to (5.3), \(n=10024\)
Rel err \(\%\)\(\mu _1\)
Rel err \(\%\)\(\mu _2\)
First run, \(m=34\)
41.87417
97.40212
Second run, \(m=25\)
2.66555
105.09263
Third run, \(m=7\)
0.05706
1.69921
6 Numerical simulations of a parameterized advection–diffusion equation
The advection–diffusion equation can be used to model particle transport, for example the distribution of air pollutants in the atmosphere; see [19, 43]. In particular, we consider the parameterized advection–diffusion equation given by
where \(f_1(\mu _1) = 1 + \sin (\mu _1)\), \(f_2 (\mu _2) = 10 + \cos (\mu _2) + \pi \mu _2\) and \(x\in [0,1]\), \(t \in [0,T]\). The boundary conditions \(u(0,t)=0\), \(u(1,t)=0\) are enforced, as well as the initial condition \(u_0(x) = u(x,0)=\sin (\pi x)\). Here, \(f_1(\mu _1)\) is referred to as the diffusion coefficient, and the value \(f_2(\mu _2)\) is the advection parameter. Discretizing (6.1) in space, with a finite difference scheme, and in time, with the implicit Euler method, gives a parameterized linear system of the form (1.1), where
Note, the solution to this linear system gives an approximation to (6.1) at a specific discrete time-step. As in Sect. 5, we construct a reduced order model via a tensor decomposition [31], where the snapshots are generated efficiently with a modified version of the method Preconditioned Chebyshev BiCG [15]. Here the sampling is performed on a sparse grid in the parameter space. If the tensor decomposition is not successful or the resulting model is not sufficiently accurate, a new set of snapshots can be generated on the same parameter space with little extra computation. These solutions can be used to attempt to build a better model. Similar model problems appear in, for example, [37], where the method PGD was used to construct approximate solutions to the parameterized PDE. Once the corresponding reduced order model (3.17) has been constructed, approximating the solutions for many \((\mu _1,\mu _2)\) can be done very cheaply; see Remark 3.4.
6.1 First simulation, snapshots sampled on a sparse grid
We construct approximations to (6.1) with Algorithm 1, where the sampling is performed as displayed in Fig. 16a. Figure 15 shows the percent relative error for approximations to (6.1) for 400 different pairs \((\mu _1,\mu _2) \in [0,0.5]\times [0,0.5]\), where, specifically, we consider the solutions at \(t=0.01\). As in [32], approximate solutions with percent relative error below \(6 \%\) are considered reliable, and approximations with percent relative error below \(1.5 \%\) are considered accurate. Here the error is computed by comparing the approximation to the solution obtained using backslash in Matlab. The 9 snapshots used to constructed the reduced order model here were generated with 2 executions of Chebyshev BiCG, requiring the LU decompositions of 2 matrices of dimension \(n \times n\).
Note, solutions to the advection–diffusion equation (6.1) are time-dependent. An all-at-once procedure could be utilized to approximate solutions to this equation at many different time-steps, though this approach would result in a larger number of unknowns and a longer simulation time. Alternatively, the decomposition could be modified to construct an approximation similar to the one in (3.3), separated in the time variable t as well as the parameters \(\mu _1\) and \(\mu _2\). Such an approach would, however, require specific testing. Furthermore, a decomposition of this form performed with HOPGD sampling on a sparse grid in the parameter space may not be optimal [31].
Fig. 15
Percent relative error of \(x^m(\mu _1,\mu _2)\) (3.18) to approximate (6.1) for 400 pairs of \((\mu _1,\mu _2)\), \(m=50\), \(n=9999\). Here accurate: \(<1.5 \%\), reliable \(<6 \%\). Note, same model in both figures
6.2 Second simulation, parameter estimation with snapshots sampled on a sparse grid
Consider again a parameter estimation problem. Specifically, we have an approximation to \(u(x,t) \in \mathbb {R}^n\) in (6.1), where \(t=0.01\) is known, but the parameters \(\mu _1\) and \(\mu _2\) are not. This approximation corresponds to the solution to the discretized problem and is obtained using backslash in Matlab. Additionally, there is some uncertainty in the measurement of the given solution. In this way, we express our observed solution \(u^{\text {obs}} \in \mathbb {R}^n\) as
where \(\Delta \in \mathcal {N}(0,I) \in \mathbb {R}^n\) is a random vector and \(\varepsilon = 10^{-2}\).
Figure 16 and Table 2 show the result of this parameter estimation problem, using a similar strategy to the one described in [33]. Here 3 successive HOPGD models are constructed from snapshots sampled on a sparse grid in the parameter space \((\mu _1,\mu _2) \in [0,0.5]\times [0,0.5]\). This simulation executes a modified version of Chebyshev BiCG 6 times, generating the 23 snapshots efficiently. Note, this requires the LU decompositions of 6 matrices of dimension \(n \times n\). After the third run of Algorithm 1, the estimated parameter is very close to the actual parameter. Note, the relative error in \(\mu _1\) and \(\mu _2\) after the third run of the simulation is of the same order of magnitude as the noise in the observed solution (6.2).
Fig. 16
Parameter estimation for noisy solution to (6.1), \(n=9999\)
Percent relative error for parameter estimation in \(\mu _1\) and \(\mu _2\) for noisy solution to (6.1), \(n=9999\)
Rel err \(\%\)\(\mu _1\)
Rel err \(\%\)\(\mu _2\)
First run, \(m=50\)
1.9004
16.1248
Second run, \(m=25\)
4.8542
23.2504
Third run, \(m=15\)
1.2313
4.2588
7 Conclusions and future work
This work overcomes the challenge of treating linear systems with dependence on multiple parameters efficiently. By generating a reduced order model for the solution using snapshots generated by carefully varying a single parameter at a time, we are able to propose a method built on the robust method for treating systems with a single-parameter dependence [15], as we can use preconditioned Chebyshev BiCG to generate many snapshots simultaneously. This allows us to to generate the snapshot solutions required to build a reduced order model in a way that is both low-cost and novel. The model is based on an efficient decomposition of a tensor matrix, where the sampling is performed on a sparse grid.
Tensor decompositions may fail to reach a certain level of accuracy on a given set of snapshot solutions. Further, reduced order models based on sampling can suffer from overfitting and underfitting, and the choice of snapshots can affect the simulation time. Our approach offers a way to generate a new set of snapshots on the same parameter space with little extra computation. This is advantageous, as it is not known a priori if a given set of snapshots will produce an accurate and robust model, and generating snapshots is computationally demanding in general. The reduced order model can also be used to solve a parameter estimation problem. Numerical simulations show competitive results.
In [31], a residual-based accelerator was used in order to decrease the number of iterations required by the fixed point method when computing the updates described in (3.10), (3.12), and (3.13). Techniques of this variety are especially effective when the snapshot solutions have a strong dependence on the parameters. Such a strategy could be directly incorporated into this work, though specific testing would be required to evaluate the benefit. Moreover, the adaptive refinement strategy presented in the same work could improve accuracy in highly oscillatory problems, and the snapshots could be generated efficiently by repeated execution of the method proposed here.
Acknowledgements
The Erasmus+ programme of the European Union funded the first author’s extended visit to Trinity College Dublin to carry out this research. The authors thank Elias Jarlebring (KTH Royal Institute of Technology) for fruitful discussions and for providing feedback on the manuscript. Additionally, the authors wish to thank Anna-Karin Tornberg (KTH Royal Institute of Technology) and her research group for many supportive, constructive discussions.
Declarations
Conflict of interest
The authors declared that they have no Conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Aguado, J.V., Huerta, A., Chinesta, F., Cueto, E.: Real-time monitoring of thermal processes by reduced-order modeling. Int. J. Numer. Methods Eng. 102, 991–1017 (2015)MathSciNetCrossRef
2.
Ahmad, M.I., Szyld, D.B., van Gijzen, M.B.: Preconditioned multishift BiCG for \(\cal{H} _2\)-optimal model reduction. SIAM J. Matrix Anal. Appl. 38, 401–424 (2017)MathSciNetCrossRef
3.
Alnaes, M.S., Blechta, J., Hake, J., Johansson, A., Kehlet, B., Logg, A., Richardson, C., Ring, J., Rognes, M.E., Wells, G.N.: The FEniCS project version 1.5. Arch. Numer. Softw. 3 (2015)
4.
Amiraslani, A., Corless, R.M., Lancaster, P.: Linearization of matrix polynomials expressed in polynomial bases. IMA J. Numer. Anal. 29, 141–157 (2009)MathSciNetCrossRef
5.
Ammar, A., Mokdad, B., Chinesta, F., Keunings, R.: A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modelling of complex fluids. J. Non-Newtonian Fluid Mech. 139, 153–176 (2006)CrossRef
6.
Ammar, A., Mokdad, B., Chinesta, F., Keunings, R.: A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modelling of complex fluids. Part II: Transient simulation using space-time separated representations. J. Non-Newtonian Fluid Mech. 144, 98–121 (2007)CrossRef
7.
Berkooz, G., Holmes, P., Lumley, J.L.: The proper orthogonal decomposition in the analysis of turbulent flows. Annu. Rev. Fluid Mech. 25, 539–575 (1993)MathSciNetCrossRef
8.
Blal, N., Gravouil, A.: Non-intrusive data learning based computational homogenization of materials with uncertainties. Comput. Mech. 64, 807–828 (2019)MathSciNetCrossRef
9.
Borzacchiello, D., Aguado, J., Chinesta, F.: Non-intrusive sparse subspace learning for parameterized problems. Arch. Comput. Methods Eng. 26, 303–326 (2017)CrossRef
Chinesta, F., Ammar, A., Cueto, E.: Recent advances and new challenges in the use of the proper generalized decomposition for solving multidimensional models. Arch. Comput. Methods Eng. 17, 327–350 (2010)MathSciNetCrossRef
12.
Chinesta, F., Ammar, A., Leygue, A., Keunings, R.: An overview of the proper generalized decomposition with applications in computational rheology. J. Non-Newtonian Fluid Mech. 116, 578–592 (2011)CrossRef
13.
Chinesta, F., Ladeveze, P., Cueto, E.: A short review on model order reduction based on proper generalized decomposition. Arch. Comput. Methods Eng. 18, 395–404 (2011)CrossRef
14.
Correnty, S., Jarlebring, E., Soodhalter, K.M.: Preconditioned infinite GMRES for parameterized linear systems. SIAM J. Sci. Comput. 46, S120-S141 (2024)
15.
Correnty, S., Jarlebring, E., Szyld, D.B.: Preconditioned Chebyshev BiCG method for parameterized linear systems. Electron. Trans. Numer. Anal. 58, 629–656 (2023)MathSciNetCrossRef
16.
Dirckx, S., Huybrechs, D., Meerbergen, K.: Frequency extraction for BEM matrices arising from the 3D scalar Helmholtz equation. SIAM J. Sci. Comput. 44, B1282–B1311 (2022)MathSciNetCrossRef
Effenberger, C., Kressner, D.: Chebyshev interpolation for nonlinear eigenvalue problems. BIT 52, 933–951 (2012)MathSciNetCrossRef
19.
Egan, B.A., Mahoney, J.R.: Numerical modeling of advection and diffusion of urban area source pollutants. J. Appl. Meteorol. (1962–1982) 11, 312–322 (1972)CrossRef
20.
Fletcher, R.: Conjugate gradient methods for indefinite systems. In: Watson, G.A. (ed.) Numerical Analysis. Lecture Notes in Mathematics, vol. 506, pp. 73–89. Springer, Berlin (1976)
21.
Freund, R.W.: Solution of Shifted Linear Systems by Quasi-minimal Residual Iterations. De Gruyter (1993)CrossRef
22.
Frommer, A.: BiCGStab(\(\ell \)) for families of shifted linear systems. Computing 70, 87–109 (2003)MathSciNetCrossRef
23.
Frommer, A., Glässner, U.: Restarted GMRES for shifted linear systems. SIAM J. Sci. Comput. 19, 15–26 (1998)MathSciNetCrossRef
24.
Haasdonk, B., Ohlberger, M., Rozza, G.: A reduced basis method for evolution schemes with parameter-dependent explicit operators. Electron. Trans. Numer. Anal. 32, 145–161 (2008)MathSciNet
Kressner, D., Roman, J.E.: Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis. Numer. Linear Algebra Appl. 21, 569–588 (2014)MathSciNetCrossRef
29.
Lanczos, C.: Solution of linear equations by minimized iterations. J. Res. Natl. Bur. Stand. 49, 33–53 (1952)MathSciNetCrossRef
30.
Lathauwer, L.D., Moor, B.D., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21, 1253–1278 (2000)MathSciNetCrossRef
31.
Lu, Y., Blal, N., Gravouil, A.: Adaptive sparse grid based HOPGD: toward a nonintrusive strategy for constructing a space-time welding computational vademecum. Int. J. Numer. Methods Eng. 114, 1438–1461 (2018)MathSciNetCrossRef
32.
Lu, Y., Blal, N., Gravouil, A.: Multi-parametric space-time computational vademecum for parametric studies: Application to real time welding simulations. Finite Elem. Anal. Des. 139, 62–72 (2018)MathSciNetCrossRef
33.
Lu, Y., Blal, N., Gravouil, A.: Datadriven HOPGD based computational vademecum for welding parameter identification. Comput. Mech. 64, 47–62 (2019)MathSciNetCrossRef
34.
Modesto, D., Zlotnik, S., Huerta, A.: Proper generalized decomposition for parameterized Helmholtz problems in heterogeneous and unbounded domains: Application to harbor agitation. Comput. Methods Appl. Mech. Eng. 295, 127–149 (2015)MathSciNetCrossRef
35.
Nadal, E., Chinesta, F., Díez, P., Fuenmayor, F.J., Denia, F.D.: Real time parameter identification and solution reconstruction from experimental data using the proper generalized decomposition. Comput. Methods Appl. Mech. Eng. 296, 113–128 (2015)MathSciNetCrossRef
36.
Nocedal, J., Wright, S.: Numerical Optimization. Springer Series (2006)
37.
Nouy, A.: A priori model reduction through Proper Generalized Decomposition for solving time-dependent partial differential equations. Comput. Methods Appl. Mech. Eng. 199, 1603–1626 (2010)MathSciNetCrossRef
38.
Oseledets, I.V., Savostianov, D.V., Tyrtyshnikov, E.E.: Tucker dimensionality reduction of three-dimensional arrays in linear time. SIAM J. Matrix Anal. Appl. 30, 939–956 (2008)MathSciNetCrossRef
39.
Peroviç, V., Mackey, D.S.: Linearizations of matrix polynomials in Newton bases. Linear Algebra Appl. 556, 1–45 (2018)MathSciNetCrossRef
40.
Signorini, M., Zlotnik, S., Díez, P.: Proper Generalized Decomposition solution of the parameterized Helmholtz problem: application to inverse geophysical problems. Int. J. Numer. Methods Eng. 109(8), 1085–1102 (2017)MathSciNetCrossRef
41.
Soodhalter, K.M., Szyld, D.B., Xue, F.: Krylov subspace recycling for sequences of shifted linear systems. Appl. Numer. Math. 81, 105–118 (2014)MathSciNetCrossRef
42.
Terán, F.D., Dopico, F.M., Mackey, S.: Fiedler companion linearizations and the recovery of minimal indices. Technical report (2009)
43.
Ulfah, S., Awalludin, S.A., Wahidin: Advection–diffusion model for the simulation of air pollution distribution from a point source emission. J. Phys.: Conf. Ser. 948, 012067 (2018)
44.
Van Beeumen, R., Meerbergen, K., Michiels, W.: Compact rational Krylov methods for nonlinear eigenvalue problems. SIAM J. Sci. Comput. 36, 820–838 (2015)MathSciNet
45.
Zlotnik, S., Díez, P., Modesto, D., Huerta, A.: Proper generalized decomposition of a geometrically parameterized heat problem with geophysical applications. Int. J. Numer. Methods Eng. 103, 737–758 (2015)CrossRef
