A memory-efficient model order reduction for time-delay systems

Michiels et al. (SIAM J. Matrix Anal. Appl. 32(4):1399–1421, 2011) proposed a Krylov-based model order reduction (MOR) method for time-delay systems. In this paper, we present an efficient process, which requires less memory consumption, to accomplish the model reduction. Memory efficiency is achieved by replacing the classical Arnoldi process in the MOR method with a two-level orthogonalization Arnoldi (TOAR) process. The resulting memory requirement is reduced from quadratic dependency of the reduced order to linear dependency. Besides, this TOAR process can also be applied to reduce the original delay system into a reduced-order delay system. Numerical experiments are given to illustrate the feasibility and effectiveness of our method.     

Two-sided harmonic subspace extractions for the generalized eigenvalue problem

One crucial step of the solution of large-scale generalized eigenvalue problems with iterative subspace methods, e.g. Arnoldi, Jacobi-Davidson, is a projection of the original large-scale problem onto a low dimensional subspaces. Here we investigate two-sided methods, where approximate eigenvalues together with their right and left eigenvectors of the full-size problem are extracted from the resulting small eigenproblem. The two-sided Ritz-Galerkin projection can be seen as the most basic form of this approach. It usually provides a good convergence towards the extremal eigenvalues of the spectrum. For improving the convergence towards interior eigenvalues, we investigate two approaches based on harmonic subspace extractions for the generalized eigenvalue problem. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithm

In this text, we present a generalization of the idea of the Implicitly Restarted Arnoldi method to the unsymmetric Lanczos algorithm, using the two-sided Gram-Schmidt process or using a full Lanczos tridiagonalization. The resulting implicitly restarted Lanczos method is called Nested Lanczos. Nested Lanczos can be combined with an implicit filter. It can also be used in case of breakdown and offers an alternative for look-ahead. This revised version was published online in August 2006 with corrections to the Cover Date.     

Parametric model order reduction of damped mechanical systems via the block Arnoldi process

This paper proposes a block Arnoldi method for parameterized model order reduction. This method works when design parameters have only low-rank impacts on the system matrix. The method preserves all design parameters in the reduced model and is easy to implement. Numerical results show that the block Arnoldi process outperforms some existing methods up to a factor of ten.     

Unitary orthogonalization processes

All methods for solving least-squares problems involve orthogonalization in one way or another. Certain fundamental estimation and prediction problems of signal processing and time-series analysis can be formulated as least-squares problems. In these problems, the sequence that is to be orthogonalized is generated by an underlying unitary operator. A prime example of an efficient orthogonalization procedure for this class of problems is Gragg's isometric Arnoldi process, which is the abstract encapsulation of a number of concrete algorithms. In this paper, we discuss a two-sided orthogonalization process that is equivalent to Gragg's process but has certain conceptual strengths that warrant its introduction. The connections with classical algorithms of signal processing are discussed.     

Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

A model order reduction technique for systems with nonlinear frequency dependent damping

Frequency domain solution of systems with frequency dependent damping is a computationally expensive endeavour especially when dealing with large order three-dimensional systems. A moment-matching based reduced order model is proposed in this work which is capable of handling nonlinear frequency dependent damping in second-order systems. In the proposed approach, local linear systems with frequency independent matrices are derived from the original system, and using the principles of the Rational Krylov approach, orthogonal basis vectors are computed from these local systems through the second-order Arnoldi procedure. The system is then projected on to the basis set to obtain a numerically efficient reduced order model, accurate in the entire frequency domain of interest. The proposed approach is also shown to be more accurate than the popular modal projection based multi-model approach of the same order. The proposed tool is applied to the problem of determining the frequency response of an idealised centrifugal compressor impeller with non-viscous (frequency dependent) damping.     

IMPROVING EIGENVECTORS IN ARNOLDI'S METHOD

1. IntroductionArnoldi's method [1, 12] is used for computing.,a few selected eigenpairs of largeunsymmetric matrices. It hajs been investigated since the 1980s; see, e-g., [3--15].It is well known that the m--step Arnoldi processt as described in detail in Section 2,generates an orthonormal basis {yi}7=1 of the Krylov subspace Km(vi, A) spanned byvil Avi,... 5 Am--'v,. Here yi is an initial unit norm vector. The projected matrix ofA onto Km(vi, A) is represented by an m x m upper Hessenb…     

Reduced order fully coupled structural–acoustic analysis via implicit moment matching

A reduced order model is developed for low frequency, undamped, fully coupled structural–acoustic analysis of interior cavities backed by flexible structural systems. The reduced order model is obtained by applying a projection of the coupled system matrices, from a higher dimensional to a lower dimensional subspace, whilst preserving essential properties of the coupled system. The basis vectors for projection are computed efficiently using the Arnoldi algorithm, which generates an orthogonal basis for the Krylov Subspace containing moments of the original system. The key idea of constructing a reduced order model via Krylov Subspaces is to remove the uncontrollable, unobservable and weakly controllable, observable parts without affecting the transfer function of the coupled system. Three computational test cases are analyzed, and the computational gains and the accuracy compared with the direct inversion method in ANSYS.     

An inexact shift‐and‐invert Arnoldi algorithm for Toeplitz matrix exponential

We revisit the shift‐and‐invert Arnoldi method proposed in [S. Lee, H. Pang, and H. Sun. Shift‐invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., 32: 774–792, 2010] for numerical approximation to the product of Toeplitz matrix exponential with a vector. In this approach, one has to solve two large‐scale Toeplitz linear systems in advance. However, if the desired accuracy is high, the cost will be prohibitive. Therefore, it is interesting to investigate how to solve the Toeplitz systems inexactly in this method. The contribution of this paper is in three regards. First, we give a new stability analysis on the Gohberg–Semencul formula (GSF) and define the GSF condition number of a Toeplitz matrix. It is shown that when the size of the Toeplitz matrix is large, our result is sharper than the one given in [M. Gutknecht and M. Hochbruck. The stability of inversion formulas for Toeplitz matrices, Linear Algebra Appl., 223/224: 307–324, 1995]. Second, we establish a relation between the error of Toeplitz systems and the residual of Toeplitz matrix exponential. We show that if the GSF condition number of the Toeplitz matrix is medium‐sized, then the Toeplitz systems can be solved in a low accuracy. Third, based on this relationship, we present a practical stopping criterion for relaxing the accuracy of the Toeplitz systems and propose an inexact shift‐and‐invert Arnoldi algorithm for the Toeplitz matrix exponential problem. Numerical experiments illustrate the numerical behavior of the new algorithm and show the effectiveness of our theoretical results. Copyright © 2015 John Wiley & Sons, Ltd.     

A framework of the harmonic Arnoldi method for evaluating <Emphasis Type="Italic">φ</Emphasis>-functions with applications to exponential integrators

In recent years, a great deal of attention has been focused on exponential integrators. The important ingredient to the implementation of exponential integrators is the efficient and accurate evaluation of the so called φ-functions on a given vector. The Krylov subspace method is an important technique for this problem. For this type of method, however, restarts become essential for the sake of storage requirements or due to computational complexities of evaluating matrix function on a reduced matrix of growing size. Another problem in computing φ-functions is the lack of a clear residual notion. The contribution of this work is threefold. First, we introduce a framework of the harmonic Arnoldi method for φ-functions, which is based on the residual and the oblique projection technique. Second, we establish the relationship between the harmonic Arnoldi approximation and the Arnoldi approximation, and compare the harmonic Arnoldi method and the Arnoldi method from a theoretical point of view. Third, we apply the thick-restarting strategy to the harmonic Arnoldi method, and propose a thick-restarted harmonic Arnoldi algorithm for evaluating φ-functions. An advantage of the new algorithm is that we can compute several φ-functions simultaneously in the same search subspace after restarting. The relationship between the error and the residual of the harmonic Arnoldi approximation is also investigated. Numerical experiments show the superiority of our new algorithm over many state-of-the-art algorithms for computing φ-functions.     

A reflection on the implicitly restarted Arnoldi method for computing eigenvalues near a vertical line

In this article, we will study the link between a method for computing eigenvalues closest to the imaginary axis and the implicitly restarted Arnoldi method. The extension to computing eigenvalues closest to a vertical line is straightforward, by incorporating a shift. Without loss of generality we will restrict ourselves here to computing eigenvalues closest to the imaginary axis.In a recent publication, Meerbergen and Spence discussed a new approach for detecting purely imaginary eigenvalues corresponding to Hopf bifurcations, which is of interest for the stability of dynamical systems. The novel method is based on inverse iteration (inverse power method) applied on a Lyapunov-like eigenvalue problem. To reduce the computational overhead significantly a projection was added.This method can also be used for computing eigenvalues of a matrix pencil near a vertical line in the complex plane. We will prove in this paper that the combination of inverse iteration with the projection step is equivalent to Sorensen’s implicitly restarted Arnoldi method utilizing well-chosen shifts.     

Heavy Ball Flexible GMRES Method for Nonsymmetric Linear Systems

Flexible GMRES (FGMRES) is a variant of preconditioned GMRES, which changes preconditioners at every Arnoldi step. GMRES often has to be restarted in order to save storage and reduce orthogonalization cost in the Arnoldi process. Like restarted GMRES, FGMRES may also have to be restarted for the same reason. A major disadvantage of restarting is the loss of convergence speed. In this paper, we present a heavy ball flexible GMRES method, aiming to recoup some of the loss in convergence speed in the restarted flexible GMRES while keep the benefit of limiting memory usage and controlling orthogonalization cost. Numerical tests often demonstrate superior performance of the proposed heavy ball FGMRES to the restarted FGMRES.     

基于分布式序关系的双边匹配决策方法

针对分布式序关系的双边匹配问题,提出了一种基于证据推理的决策方法。首先,以双边匹配满意程度为目标,把双边的各个评价信息作为证据,并通过证据融合求出匹配的满意度;接着,构建基于满意度的决策模型来获得匹配方案。最后, 通过算例说明该方法的应用。     

A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations

In the present paper, we propose a preconditioned Newton–Block Arnoldi method for solving large continuous time algebraic Riccati equations. Such equations appear in control theory, model reduction, circuit simulation amongst other problems. At each step of the Newton process, we solve a large Lyapunov matrix equation with a low rank right hand side. These equations are solved by using the block Arnoldi process associated with a preconditioner based on the alternating direction implicit iteration method. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approach.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

Exponential behaviour of the Butkovi?-Zimmermann algorithm for solving two-sided linear systems in max-algebra

In [P. Butkovi?, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437-446] an ingenious algorithm for solving systems of two-sided linear equations in max-algebra was given and claimed to be strongly polynomial. However, in this note we give a sequence of examples showing exponential behaviour of the algorithm. We conclude that the problem of finding a strongly polynomial algorithm is still open.     

Structure preserving quaternion full orthogonalization method with applications

This article proposes a structure-preserving quaternion full orthogonalization method (QFOM) for solving quaternion linear systems arising from color image restoration. The method is based on the quaternion Arnoldi procedure preserving the quaternion Hessenberg form. Combining with the preconditioning techniques, we further derive a variant of the QFOM for solving the linear systems, which can greatly improve the rate of convergence of QFOM. Numerical experiments on randomly generated data and color image restoration problems illustrate the effectiveness of the proposed algorithms in comparison with some existing methods.     

考虑匹配意愿的直觉模糊双边匹配决策

本文从匹配意愿的视角研究了基于直觉模糊集信息的双边匹配问题。首先给出了直觉模糊集和双边匹配的概念;接着描述了考虑匹配意愿的直觉模糊双边匹配问题。为求解该问题,先将直觉模糊集矩阵转化为得分矩阵。以每个主体得分最大为目标,在一对一双边匹配约束条件下,建立了双边匹配模型。依据得分矩阵,计算匹配意愿矩阵;依据匹配意愿矩阵,将双边匹配模型转化为单目标优化模型;通过求解该模型获得“最佳”双边匹配。最后,通过一个人岗匹配实例说明了所提双边匹配决策的可行性和有效性。