- P. Benner,
**S. Gugercin**, and K. Willcox. "*A Survey of Projection-Based Model Reduction Methods for Parametric Dynamical Systems.*" SIAM Review, Vol. 57, Issue: 4, pp. 483-531, 2015. - B. Peherstorfer,
**S. Gugercin**, and K. Willcox.*"Data-driven Reduced Model Construction with Time-domain Loewner Models.*"Accepted to appear in SIAM Journal on Scientific Computing, 2017. Available as Aerospace Computational Design Laboratory, Massachusetts Institute of Technology, Technical Report 16-5, 2016.Click for AbstractThis work presents a data-driven nonintrusive model reduction approach for large-scale time-dependent systems with linear state dependence. Traditionally, model reduction is performed in an intrusive projection-based framework, where the operators of the full model are required either explicitly in an assembled form or implicitly through a routine that returns the action of the operators on a vector. Our nonintrusive approach constructs reduced models directly from trajectories of the inputs and outputs of the full model, without requiring the full-model operators. These trajectories are generated by running a simulation of the full model; our method then infers frequency response data from these simulated time-domain trajectories and uses the data-driven Loewner framework to derive a reduced model. Only a single time-domain simulation is required to derive a reduced model with the new data-driven nonintrusive approach. We demonstrate our model reduction method on several benchmark examples and a finite element model of a cantilever beam; our approach recovers the classical Loewner reduced models and, for these problems, yields high-quality reduced models despite treating the full model as a black box -
P. Schulze, B. Unger, C. Beattie, and S Gugercin."
*Data-driven Structured Realization*". Submitted 2016. Available as arXiv:1611.02072.Click for AbstractWe present a framework for constructing structured realizations of linear dynamical systems having transfer functions of the form $C(\sum_{k=1}^K h_k(s)\A_k)^{-1}\B$ where $h_1,\,h_2,\,...,h_K$ are prescribed functions that specify the surmised structure of the model. Our construction is data-driven in the sense that an interpolant is derived entirely from measurements of a transfer function. Our approach extends the Loewner realization framework to more general system structure that includes second-order (and higher) systems as well as systems with internal delays. Numerical examples demonstrate the advantages of this approach. - P. Benner, P. Goyal, and
**S. Gugercin**. "*H_2 -Quasi-Optimal Model Order Reduction for Quadratic-Bilinear Control Systems.*" Submitted 2016. Available as arXiv:1610.03279.Click for AbstractWe investigate the optimal model reduction problem for large-scale quadratic-bilinear (QB) control systems. Our contributions are threefold. First, we define a truncated H_2-norm for QB systems based on the leading kernels of the underlying Volterra series. We then derive the first-order necessary conditions for an optimal approximation, minimizing the truncated H_2-norm of the error system by utilizing tensor algebra. This allows us to propose an iterative model reduction algorithm, which upon convergence yields a reduced-order system that approximately satisfies the derived optimality conditions. We also discuss an efficient computation of the reduced Hessian, using the special Kronecker structure of the Hessian of the system. We illustrate the efficiency of the proposed method by means of several numerical examples resulting from semi-discretized nonlinear partial differential equations, and show its competitiveness with the existing model reduction schemes for QB systems such as moment-matching methods and balanced truncation. - C. Beattie,
**S. Gugercin**and V. Mehrmann. "Click for AbstractWe consider the model reduction problem for linear time-invariant dynamical systems having nonzero (but otherwise indeterminate) initial conditions. Building upon the observation that the full system response is decomposable as a superposition of the response map for an unforced system having nontrivial initial conditions and the response map for a forced system having null initial conditions, we develop a new approach that involves reducing these component responses independently and then combining the reduced responses into an aggregate reduced system response. This approach allows greater flexibility and offers better approximation properties than other comparable methods. - M. O'Connell, M. Kilmer, E. de Sturler, and S. Gugercin. "Computing Reduced Order Models via Inner-Outer Krylov Recycling in Diffuse Optical Tomography". SIAM Journal on Scientific Computing, Vol. 39, No. 2, pp. B272-B297, 2017.
Click for AbstractIn nonlinear imaging problems whose forward model is described by a partial differential equation (PDE), the main computational bottleneck in solving the inverse problem is the need to solve many large-scale discretized PDEs at each step of the optimization process. In the context of absorption imaging in diffuse optical tomography, one approach to addressing this bottleneck proposed recently (de Sturler, et al, 2015) reformulates the viewing of the forward problem as a differential algebraic system, and then employs model order reduction (MOR). However, the construction of the reduced model requires the solution of several full order problems (i.e. the full discretized PDE for multiple right-hand sides) to generate a candidate global basis. This step is then followed by a rank-revealing factorization of the matrix containing the candidate basis in order to compress the basis to a size suitable for constructing the reduced transfer function. The present paper addresses the costs associated with the global basis approximation in two ways. First, we use the structure of the matrix to rewrite the full order transfer function, and corresponding derivatives, such that the full order systems to be solved are symmetric (positive definite in the zero frequency case). Then we apply MOR to the new formulation of the problem. Second, we give an approach to computing the global basis approximation dynamically as the full order systems are solved. In this phase, only the incrementally new, relevant information is added to the existing global basis, and redundant information is not computed. This new approach is achieved by an inner-outer Krylov recycling approach which has potential use in other applications as well. We show the value of the new approach to approximate global basis computation on two DOT absorption image reconstruction problems.
- C. Magruder, C. Beattie,
**S. Gugercin.**"*Linear time-periodic dynamical systems: An H2 analysis and a model reduction framework.*" Submitted, 2016.Click for AbstractLinear time-periodic (LTP) dynamical systems frequently appear in the modeling of phenomena related to fluid dynamics, electronic circuits, and structural mechanics via linearization centered around known periodic orbits of nonlinear models. Such LTP systems can reach orders that make repeated simulation or other necessary analysis prohibitive, motivating the need for model reduction.

We develop here an algorithmic framework for constructing reduced models that retains the linear time-periodic structure of the original LTP system. Our approach generalizes optimal approaches that have been established previously for linear time-invariant (LTI) model reduction problems. We employ an extension of the usual H2 Hardy space defined for the LTI setting to time-periodic systems and within this broader framework develop an a posteriori error bound expressible in terms of related LTI systems. Optimization of this bound motivates our algorithm. We illustrate the success of our method on two numerical examples. - S. Chaturantabut, C. Beattie, and
**S. Gugercin**. "*Structure-preserving Model Reduction for Nonlinear Port-Hamiltonian Systems*". SIAM Journal on Scientific Computing, Vol. 38, No. 5, pp. B837-B865, 2016.Click for AbstractThis paper presents a structure-preserving model reduction approach applicable to large-scale, nonlinear port-Hamiltonian systems. Structure preservation in the reduction step ensures the retention of port-Hamiltonian structure which, in turn, assures the stability and passivity of the reduced model. Our analysis provides a priori error bounds for both state variables and outputs. Three techniques are considered for constructing bases needed for the reduction: one that utilizes proper orthogonal decompositions; one that utilizes

*H*_{2}/*H*_{∞}-derived optimized bases; and one that is a mixture of the two. The complexity of evaluating the reduced nonlinear term is managed efficiently using a modification of the discrete empirical interpolation method (DEIM) that also preserves port-Hamiltonian structure. The efficiency and accuracy of this model reduction framework are illustrated with two examples: a nonlinear ladder network and a tethered Toda lattice. - Z. Drmac and
**S. Gugercin**. "*A New Selection Operator for the Discrete Empirical Interpolation Method -- improved a priori error bound and extensions.*" SIAM Journal on Scientific Computing, Vol. 38, No. 2, pp. A631-A648, 2016.Click for AbstractThis paper introduces a new framework for constructing the Discrete Empirical Interpolation Method (DEIM) projection operator. The interpolation nodes selection procedure is formulated using a QR factorization with column pivoting. This selection strategy leads to a sharper error bound for the DEIM projection error and works on a given orthonormal frame U as a point on the Stiefel manifold, i.e., the selection operator does not change if U is replaced by UQ with arbitrary unitary matrix Q. The new approach allows modifications that, in the case of gargantuan dimensions, use only randomly sampled rows of U but are capable of producing equally good approximations. - B. Kramer and
**S. Gugercin**. " The Eigensystem Realization Algorithm from Tangentially Interpolated Data". Mathematical and Computer Modelling of Dynamical Systems, Vol. 22, Issue. 4, pp. 282-306, 2016.Click for AbstractThe Eigensystem Realization Algorithm (ERA) is a commonly used data-driven method for system identification and reduced-order modeling of dynamical systems. The main computational difficulty in ERA arises when the system under consideration has a large number of inputs and outputs, requiring to compute an SVD of a large-scale dense Hankel matrix. In this work, we present an algorithm that aims to resolve this computational bottleneck via tangential interpolation. This involves projecting the original impulse response sequence onto suitably chosen directions. The resulting data-driven reduced-model preserves stability and is endowed with an a priori error bound. Numerical examples demonstrate that the modified ERA algorithm with tangentially interpolated data produces accurate reduced models while, at the same time, reducing the computational cost and memory requirements significantly compared to the standard ERA. We also give an example to demonstrate the limitations of the proposed method. - Z. Drmac,
**S. Gugercin**and C.A. Beattie. "*Vector Fitting for Matrix-valued Rational Approximation.*" Accepted to appear in SIAM Journal on Scientific Computing 2015. SIAM Journal on Scientific Computing, Vol. 37, Issue: 5, pp. A2151-S626, 2015.Click for AbstractVector Fitting (VF) is a popular method of constructing rational approximants that provides a least squares fit to frequency response measurements. In an earlier work, we provided an analysis of VF for scalar-valued rational functions and established a connection with optimal H

_{2}approximation. We build on this work and extend the previous framework to include the construction of effective rational approximations to \emph{matrix-valued} functions, a problem which presents significant challenges that do not appear in the scalar case. Transfer functions associated with multi-input/multi-output (MIMO) dynamical systems typify the class of functions that we consider here. Others have also considered extensions of VF to matrix-valued functions and related numerical implementations are readily available. However to our knowledge, a detailed analysis of numerical issues that arise does not yet exist. We offer such an analysis including critical implementation details here.One important issue that arises for VF on matrix-valued functions that has remained largely unaddressed is the control of the McMillan degree of the resulting rational approximant; the McMillan degree can grow very high in the case of large input/output dimensions. We introduce two new mechanisms for controlling the McMillan degree of the final approximant, one based on alternating least-squares minimization and one based on ancillary system-theoretic reduction methods. Motivated in part by our earlier work on the scalar VF problem as well as by recent innovations for computing optimal H

_{2}approximation, we establish a connection with optimal H_{2}approximation, and are able to improve significantly the fidelity of VF through numerical quadrature, with virtually no increase in cost or complexity. We provide several numerical examples to support the theoretical discussion and proposed algorithms. -
Z. Drmac,
**S. Gugercin**and C.A. Beattie. "*Quadrature-Based Vector Fitting For Discretized H*" SIAM Journal on Scientific Computing, Vol. 37, Issue: 2, A625–A652, 2015._{2}Approximation.Click for AbstractVector Fitting is a popular method of constructing rational approximants designed to fit given frequency response measurements. The original method, which we refer to as VF, is based on a least-squares fit to the measurements by a rational function, using an iterative reallocation of the poles of the approximant. We show that one can improve the performance of VF significantly, by using a particular choice of frequency sampling points and properly weighting their contribution based on quadrature rules that connect the least squares objective with an H2 error measure. Our modified approach, designated here as QuadVF, helps recover the original transfer function with better global fidelity (as measured with respect to the H2 norm), than the localized least squares approximation implicit in VF. We extend the new framework also to incorporate derivative information, leading to rational approximants that minimize system error with respect to a discrete Sobolev norm. We consider the convergence behavior of both VF and QuadVF as well, and evaluate potential numerical ill-conditioning of the underlying least-squares problems. We investigate briefly VF in the case of noisy measurements and propose a new formulation for the resulting approximation problem. Several numerical examples are provided to support the theoretical discussion. -
G. Flagg and
**S. Gugercin**. "*Multipoint Volterra Series Interpolation and H*" SIAM Journal on Matrix Analysis and Applications, Vol. 36, Issue: 2, 549–579, 2015._{2}Optimal Model Reduction of Bilinear Systems.Click for AbstractIn this paper, we focus on model reduction of large-scale bilinear systems. The main contributions are threefold. First, we introduce a new framework for interpolatory model reduction of bilinear systems. In contrast to the existing methods where interpolation is forced on some of the leading subsystem transfer functions, the new framework shows how to enforce multipoint interpolation of the underlying Volterra series. Then, we show that the first-order conditions for optimal H2 model reduction of bilinear systems require multivariate Hermite interpolation in terms of the new Volterra series interpolation framework; and thus we extend the interpolation-based first-order necessary conditions for H2 optimality of LTI systems to the bilinear case. Finally, we show that multipoint interpolation on the truncated Volterra series representation of a bilinear system leads to an asymptotically optimal approach to H2 optimal model reduction, leading to an efficient model reduction algorithm. Several numerical examples illustrate the effectiveness of the proposed approach. - E. de Sturler,
**S. Gugercin**, M. E. Kilmer, S. Chaturantabut, C. Beattie, and M. O'Connell. "*Nonlinear Parametric Inversion using Interpolatory Model Reduction.*" SIAM Journal on Scientific Computing, Vol. 37, Issue: 3, B495–B517, 2015. - T. Breiten, C. Beattie, and
**S. Gugercin**. "*Near-optimal Frequency-weighted Interpolatory Model Reduction.*" Systems and Control Letters. Vol. 78, pp. 8–18. **S. Gugercin**, T. Stykel, and S. Wyatt. "*Model Reduction of Descriptor Systems by Interpolatory Projections Methods."*SIAM Journal on Scientific Computing, Vol. 35, Iss. 5, pp. B1010-B1033, 2013.- G. Flagg and
**S. Gugercin**. "*On the ADI method for the Sylvester Equation and the optimal-H*Applied Numerical Mathematics, Vol. 64, pp. 50-58, 2013._{2}points."

- B. Anic, C.A. Beattie,
**S. Gugercin**and A.C. Antoulas.*"Interpolatory Weighted-H*." Automatica, Vol. 49, Iss. 5, pp. 1275-1280, 2013._{2}Model Reduction - G. Flagg, C.A. Beattie and
**S. Gugercin**,*"Convergence of the Iterative Rational Krylov Algorithm*", Systems and Control Letters, Volume: 61, Issue: 6, pp. 688-691, 2012. - G. Flagg, C.A. Beattie and
**S. Gugercin**. "*Interpolatory H-infinity Model Reduction*," Systems and Control Letters, Vol. 62, Iss. 7, pp. 567-574, 2013. - K. Ahuja, E. de Sturler, R. Chang and
**S. Gugercin**, "*Recycling BiCG with an Application to Model Reduction"*, SIAM Journal on Scientific Computing, Vol. 34, Issue: 4, pp. A1925-A949, 2012. **S. Gugercin**, R. V. Polyuga, C.A. Beattie and A. van der Schaft,*"Structure-preserving tangential-interpolation based model reduction of port-Hamiltonian Systems*." Automatica, Vol. 48, Issue: 9, pp. 1963-1974, 2012.- C.A. Beattie,
**S. Gugercin**, and S. Wyatt,*"Inexact Solves in Interpolatory Model Reduction".*Linear Algebra and its Applications, Vol. 436, Issue: 8, pp. 2916-2943, 2012. - C.A. Beattie, Z. Drmac, and
**S. Gugercin**,*A note on shifted Hessenberg systems and frequency response computation,*ACM Transaction on Mathematical Software, Vol 38, No. 2, 2011.

- U. Baur, C.A. Beattie, P. Benner and
**S. Gugercin**,*"Interpolatory Projection Methods for Parameterized Model Reduction"*. SIAM Journal on Scientific Computing, Vol. 33, Issue: 5, pp. 2489-2518, 2011. - C.A. Beattie and
**S. Gugercin**,*"Interpolatory Projection Methods for Structure-preserving Model Reduction".*Systems and Control Letters, Vol. 58, Issue: 3, pp: 225–232, 2009. **S. Gugercin**, A.C. Antoulas and C.A. Beattie,*"H*SIAM Journal on Matrix Analysis and Applications Vol. 30, Issue: 2, pp. 609-638, (2008)._{2}model reduction for large-scale linear dynamical systems".**S. Gugercin**, "*An iterative SVD-Krylov based algorithm for model reduction of large-scale dynamical systems*", Linear Algebra and its Applications Vol. 428 No: 8-9 pp. 1964-1986 (2008).**S. Gugercin**and K. Willcox,*"Krylov projection framework for Fourier model reduction*", Automatica Vol. 44 No:1 pp. 209-215 (2008) .

**S. Gugercin**and A.C. Antoulas. "*Model reduction of large-scale systems by least squares*", Linear Algebra and its Applications, Special Issue on Order Reduction of Large-Scale Systems, Vol. Vol: 415 No:2-3, pp. 290-321 (2006).

**S. Gugercin**and A.C. Antoulas.*A survey of model reduction by balanced truncation and some new results.*International Journal of Control, Vol: 77 No: 8, pp. 748-766 (2004) (Copyright Taylor & Francis, 2004)**S. Gugercin**, A.C. Antoulas, and H.P. Zhang. "*An approach to identification for robust control*", IEEE Transactions on Automatic Control, Vol. 48 No: 6 pp. 1109-1115 (2003).-
**S. Gugercin**, D.C. Sorensen, and A.C. Antoulas. "*A modified low-rank Smith method for large-scale Lyapunov Equations*", Numerical Algorithms, Vol. 32, No: 1, pp. 27-55, (2003). - A.C. Antoulas, D.C. Sorensen, and
**S. Gugercin**.*A survey of model reduction methods for large-scale systems*. Structured Matrices in Operator Theory, Numerical Analysis, Control, Signal and Image Processing, Contemporary Mathematics, AMS publications, 280: 193-219, 2001. (Copyright AMS, 2001)

Click for Abstract

Numerical simulation of large-scale dynamical systems plays a
fundamental role in studying a wide range of complex physical
phenomena; however, the inherent large-scale nature of the models
often leads to unmanageable demands on computational resources. Model
reduction aims to reduce this computational burden by generating
reduced models that are faster and cheaper to simulate, yet accurately
represent the original large-scale system behavior. Model reduction of
linear, non-parametric dynamical systems has reached a considerable
level of maturity, as reflected by several survey papers and
books. However, parametric model reduction has emerged only more
recently as an important and vibrant research area, with several
recent advances making a survey paper timely. Thus, this paper aims to
provide a resource that draws together recent contributions in
different communities to survey state of the art in parametric model
reduction methods.

Parametric model reduction targets the broad class of problems for which the equations governing the system behavior depend on a set of parameters. Examples include parameterized partial differential equations and large-scale systems of parameterized ordinary differential equations. The goal of parametric model reduction is to generate low cost but accurate models that characterize system response for different values of the parameters. This paper surveys state-of-the-art methods in projection-based parametric model reduction, describing the different approaches within each class of methods for handling parametric variation and providing a comparative discussion that lends insights to potential advantages and disadvantages in applying each of the methods. We highlight the important role played by parametric model reduction in design, control, optimization, and uncertainty quantification---settings that require repeated model evaluations over different parameter values.

Parametric model reduction targets the broad class of problems for which the equations governing the system behavior depend on a set of parameters. Examples include parameterized partial differential equations and large-scale systems of parameterized ordinary differential equations. The goal of parametric model reduction is to generate low cost but accurate models that characterize system response for different values of the parameters. This paper surveys state-of-the-art methods in projection-based parametric model reduction, describing the different approaches within each class of methods for handling parametric variation and providing a comparative discussion that lends insights to potential advantages and disadvantages in applying each of the methods. We highlight the important role played by parametric model reduction in design, control, optimization, and uncertainty quantification---settings that require repeated model evaluations over different parameter values.

Click for Abstract

Nonlinear parametric inverse problems appear in several prominent applications; one such application is Diffuse Optical Tomography (DOT) in medical image reconstruction. Such inverse problems present huge computational challenges, mostly due to the need for solving a sequence of large-scale discretized, parametrized, partial differential equations (PDEs) in the forward model. In this paper, we show how interpolatory parametric model reduction can significantly reduce the cost of the inversion process in DOT by drastically reducing the computational cost of solving the forward problems. The key observation is that function evaluations for the underlying optimization problem may be viewed as transfer function evaluations along the imaginary axis; a similar observation holds for Jacobian evaluations as well. This motivates the use of system-theoretic model order reduction methods. We discuss the construction and use of interpolatory parametric reduced models as surrogates for the full forward model. Within the DOT setting, these surrogate models can approximate both the cost functional and the associated Jacobian with very little loss of accuracy while significantly reducing the cost of the overall inversion process. Four numerical examples illustrate the efficiency of the proposed approach. Although we focus on DOT in this paper, we believe that our approach is applicable much more generally.

Click for Abstract

This paper extends an interpolatory framework for weighted-H2 model reduction to MIMO dynamical systems. A new representation of the weighted-H2 inner product in MIMO settings is presented together with associated first-order
necessary conditions for an optimal weighted-H2 reduced-order model. Equivalence of these conditions with necessary conditions given by Halevi is shown. An examination of realizations for equivalent weighted-H2 systems leads to an algorithm that remains tractable for large state-space dimension. Several numerical examples illustrate the effectiveness of this approach and its competitiveness with Frequency Weighted Balanced Truncation and Weighted Iterative Rational Krylov Algorithm.

Click for Abstract

In this paper, we investigate interpolatory projection framework for model reduction of descriptor systems. With a simple numerical example, we firstillustrate that employing subspace conditions from the standard state space settings to descriptor systems generically leads to unbounded H2 or H-infinity errors due to the mismatch of the polynomial parts of the full and reduced-order transfer functions. We then develop modified interpolatory subspace conditions based on the deflating subspaces that guarantee a bounded error. For the special cases of index-1 and index-2 descriptor systems, we also show how to avoid computing these deflating subspaces explicitly while still enforcing interpolation. The question of how to choose interpolation points optimally naturally arises as in the standard state space setting. We answer this question in the framework of the H2-norm by extending the Iterative Rational Krylov Algorithm (IRKA) to descriptor systems. Several numerical examples are used to illustrate the theoretical discussion

Click for Abstract

The ADI iteration is closely related to rational Krylov projection methods for constructing low rank approximations to the solution of Sylvester equations. In this paper we show that the ADI and rational Krylov approximations are in fact equivalent when a special choice of shifts are employed in both methods. We will call these shifts pseudo H2-optimal shifts. These shifts are also optimal in the sense that they yield a residual in the Lyapunov equation which is orthogonal to the rational Krylov projection subspace. Via several examples, we show that the pseudo H2-optimal shifts consistently yield nearly optimal low rank approximations to the solutions of the Lyapunov equations.

Click for Abstract

This paper introduces an interpolation framework for the weighted-H2 model reduction problem. We obtain a new representation of the weighted-H2 norm of SISO systems that provides new interpolatory first order necessary conditions for an optimal reduced-order model. The H2 norm representation also provides an error expression that motivates a new weighted-H2 model reduction algorithm. Several numerical examples illustrate the effectiveness of the proposed approach.

Click for Abstract

Iterative Rational Krylov Algorithm (IRKA) of [8] is an interpolatory model reduction approach to optimal $\Htwo$ approximation problem. Even though the method has been illustrated to show rapid convergence in various examples, a proof of convergence has not been provided yet. In this note, we show that in the case of state-space symmetric systems, IRKA is a locally convergent fixed point iteration to a local minimum of the underlying $\Htwo$ approximation problem.

Click for Abstract

We introduce an interpolation framework for $\Hinf$ model reduction founded on ideas originating in optimal-$\Htwo$ interpolatory model reduction, realization theory, and complex Chebyshev approximation. By employing a Loewner ``data-driven" framework within each optimization cycle, large-scale $\Hinf$ norm calculations can be completely avoided. Thus, we are able to formulate a method that remains effective in large-scale settings with the main cost dominated by sparse linear solves. Several numerical examples illustrate that our approach will produce high fidelity reduced models consistently exhibiting better $\Hinf$ performance than those produced by balanced truncation; these models often are as good as (and occasionally better than) those models produced by optimal Hankel norm approximation. In all cases, these reduced models are produced at far lower cost than is possible either with balanced truncation or optimal Hankel norm approximation.

Click for Abstract

Science and engineering problems frequently require solving a sequence of dual linear systems. Besides the benefit of only having to store few Lanczos vectors, using BiConjugate Gradient (BiCG) to solve dual linear systems may have application-specific advantages. For example, using BiCG to solve the dual linear systems arising in interpolatory model reduction provides a backward error formulation in the model reduction framework. Using BiCG to evaluate bilinear forms – for example, in quantum Monte Carlo (QMC) methods for electronic structure calculations – leads to a quadratic error bound. Since the focus is on sequences of dual linear systems, we introduce recycling
BiCG, a BiCG method that recycles two Krylov subspaces from one pair of dual linear systems to the next pair. The derivation of recycling BiCG also builds the foundation for developing recycling variants of other bi-Lanczos based methods like CGS, BiCGSTAB, QMR, and TFQMR. We develop an augmented bi-Lanczos algorithm and a modified two-term recurrence to include recycling in the iteration. The recycle spaces are approximate left and right invariant subspaces corresponding to the eigenvalues close to the origin. These recycle spaces are found by solving a small generalized eigenvalue problem alongside the dual linear systems being solved in the sequence. We test our algorithm in two application areas. First, we solve a discretized partial differential equation (PDE) of the convection-diffusion type. This PDE problem provides well-known test cases that are easy to analyze further. Second, we use recycling BiCG in iterative rational Krylov algorithm (IRKA) for interpolatory model reduction. IRKA requires solving sequences of slowly changing dual linear systems. We analyze the generated recycle spaces and show up to 70% savings in iterations. For a model reduction problem, we show that solving the problem without recycling leads to (about) a 50% increase in runtime.

Click for Abstract

Port-Hamiltonian systems result from port-based network modeling of physical systems and are an important example of passive state-space systems. In this paper, we develop the framework for model reduction of large-scale multi-input/multi-output port-Hamiltonian systems via tangential rational interpolation. The resulting reduced-order model not only is a rational tangential interpolant but also retains the port-Hamiltonian structure; hence is passive. This reduction methodology is described in both energy and co-energy system coordinates. We also introduce an $\Htwo$-inspired algorithm for effectively choosing the interpolation points and tangential directions. The algorithm leads a reduced port-Hamiltonian model that satisfies a subset of $\Htwo$-optimality conditions. We present several numerical examples that illustrate the effectiveness of the proposed method showing that it outperforms other existing techniques in both quality and numerical efficiency.

Click for Abstract

We investigate the use of inexact solves for interpolatory model reduction and consider associated perturbation effects on the underlying model reduction problem. We give bounds on system perturbations induced by inexact solves and relate this to termination criteria from iterative solution methods. We show that when a Petrov-Galerkin framework is employed for the inexact solves, the inexact interpolatory reduced model is an exact interpolant for a nearby full-order model; hence providing a backward error formulation. We also give evidence that for ${\mathcal H}_2$-optimal interpolation points, interpolatory model reduction is robust with respect to the perturbations due to inexact solves. Finally, we demonstrate the use of inexact solves for optimal ${\mathcal H}_2$ approximation. The result is an effective model reductionstrategy that is applicable in realistically large-scale settings.

Click for Abstract

In this note we propose a numerical algorithm for efficient and robust solution of a sequence of shifted Hessenberg linear systems. In particular, we show how the frequency response G(s) =C(sI − A)^{−1}B + D can be computed more efficiently than with other state-of-the-art methods We also provide a backward stability analysis of the proposed algorithm.

Click for Abstract

We provide a unifying projection-based framework for structure-preserving interpolatory model reduction of parameterized linear dynamical systems, i.e., systems having a structured dependence on parameters that we wish to retain in the reduced-order model. The parameter dependence may be linear or nonlinear and is retained in the reduced-order model. Moreover, we are able to give conditions under which the gradient and Hessian of the system response with respect to the system parameters is matched in the reduced-order model. We provide a systematic approach built on established interpolatory $\mathcal{H}_2$ optimal model reduction methods that will produce parameterized reduced-order models having high fidelity throughout a parameter range of interest. For single input/single output systems with parameters in the input/output maps, we provide reduced-order models that are \emph{optimal} with respect to an $\mathcal{H}_2\otimes\mathcal{L}_2$ joint error measure. The capabilities of these approaches are illustrated by several numerical examples from technical applications.

Click for Abstract

We present and illustrate a framework for interpolatory model reduction that includes rational Krylov-based methods as a special case. This broader framework allows retention of special structure in the reduced models such as symmetry, higher order structure, state constraints, internal delays, and infinite dimensional subsystems. A numerical example is provided for a system with an internal state delay that demonstrates the effectiveness and flexibility of the approach.

Click for Abstract

The optimal H2 model reduction problem is of great importance in the area of dynamical systems and simulation. In the literature, two independent frameworks have evolved focussing either on solution of Lyapunov equations on the one hand or interpolation of transfer functions on the other, without any apparent connection between the two approaches. In this paper, we develop a new unifying framework for the optimal H2 approximation problem using best approximation properties in the underlying Hilbert space. This new framework leads to a new set of local optimality conditions taking the form of a structured orthogonality condition. We show that the existing Lyapunov and interpolation based conditions are each equivalent to our conditions and so are equivalent to each other. Also, we provide a new elementary proof of the interpolation based condition that clarifies the importance of the mirror images of the reduced system poles. Based on the interpolation framework, we describe an iteratively corrected rational Krylov algorithm for H2 model reduction. The formulation is based on finding a reduced order model that satisfies interpolation based first-order necessary conditions for H2 optimality and results in a method that is numerically effective and suited for large-scale problems. We illustrate the performance of the method with a variety of numerical experiments and comparisons with existing methods.

Click for Abstract

In this paper, we propose a model reduction algorithm for approximation of large-scale linear time-invariant dynamical systems. The method is a two-sided projection combining features of the singular value decomposition (SVD)-based and the Krylov-based model reduction techniques. While the SVD-side of the projection depends on the observability gramian, the Krylov-side is obtained via iterative rational Krylov steps. The reduced model is asymptotically stable, matches certain moments and solves a restricted $\h2$ minimization problem. We present modifications to the proposed approach for employing low-rank gramians in the reduction step and also for reducing discrete-time systems. Several numerical examples from various disciplines verify the effectiveness of the proposed approach. It performs significantly better than the {\bf q cover} \} and the {\bf least-squares} methods that have a similar projection structure to the proposed method. Also, in terms of both the $\h2$ and $\hinf$ error measures, its performance is comparable to or sometimes better than that of balanced truncation. Moreover, the method proves to be robust with respect to the perturbations due to usage of approximate gramians.

Click for Abstract

This paper analyzes the Fourier model reduction (FMR) method from a rational Krylov projection framework and shows how the FMR reduced model, which has guaranteed stability and a global error bound, can be computed in a numerically efficient and robust manner. By monitoring the rank of the Krylov subspace that underlies the FMR model, the projection framework also provides an improved criterion for determining the number of Fourier coefficients that are needed, and hence the size of the resulting reduced-order model. The advantages of applying FMR in the rational Krylov projection framework are demonstrated on a simple example.

Click for Abstract

In this paper we introduce an approximation method for model reduction of large-scale dynamical systems. This is a projection which combines aspects of the SVD and Krylov based reduction methods. This projection can be efficiently computed using tools from numerical analysis, namely the rational Krylov method for the Krylov side of the projection and a low-rank Smith type iteration to solve a Lyapunov equation for the SVD side of the projection. For discrete time systems, the proposed approach is based on the least squares fit of the $(r+1)^{st}$ column of a Hankel matrix to the preceding $r$ columns, where $r$ is the order of the reduced system. The reduced system is asymptotically stable, matches the first $r$ Markov parameters of the full order model and minimizes a weighted $\cH_2$ error. The method is also generalized for moment matching at arbitrary interpolation points. Application to continuous time systems is achieved via the bilinear transformation. Numerical examples prove the effectiveness of the approach. The proposed method is significant because it combines guaranteed stability and moment matching, together with an optimization criterion.

Click for Abstract

Balanced truncation is one of the most common model reduction schemes. In this note, we present a survey of balancing related model reduction methods and their corresponding error norms, and also introduce some new results. Five balancing methods are studied: {\bf (1)} Lyapunov balancing, {\bf (2)} Stochastic balancing {\bf (3)} Bounded real balancing, {\bf (4)} Positive real balancing and {\bf (5)} Frequency weighted balancing. For positive real balancing, we introduce a multiplicative-type error bound. Moreover, for a certain subclass of positive real systems, a modified positive-real balancing scheme with an absolute error bound is proposed. We also develop a new frequency-weighted balanced reduction method with a simple bound on the error system based on the frequency domain representations of the system gramians. Two numerical examples are illustrated to verify the efficiency of the proposed methods.

Click for Abstract

Given measured data generated by a discrete-time linear system we propose a model consisting of a linear, time-invariant system affected by norm-bounded perturbation. Under mild assumptions, the plants belonging to the resulting uncertain family form a convex set. The approach depends on two key parameters: an a priori given bound of the perturbation, and the input used to generate the data. It turns out that the size of the uncertain family can be reduced by intersecting the model families obtained by making use of different inputs. The model validation problem in this identification scheme is analyzed. For a given energy level, the invalidation problem yields the family of those models which can never be invalidated for any possible input of fixed energy and any possible perturbation; this leads to the intersection of all uncertain families. A consequence of the invalidation problem is that for finite length measurements {\it not} all models can be invalidated, using fixed-energy inputs.

Click for Abstract

Click for Abstract

An overview of model reduction methods and a comparison of the resulting algorithms is presented. These approaches are divided into two broad categories, namely SVD based and moment matching based methods. It turns out that the approximation error in the former case behaves better globally in frequency while in the latter case the local behavior is better.