Algebraic analysis of aggregation‐based multigrid

A convergence analysis of two‐grid methods based on coarsening by (unsmoothed) aggregation is presented. For diagonally dominant symmetric (M‐)matrices, it is shown that the analysis can be conducted locally; that is, the convergence factor can be bounded above by computing separately for each aggregate a parameter, which in some sense measures its quality. The procedure is purely algebraic and can be used to control a posteriori the quality of automatic coarsening algorithms. Assuming the aggregation pattern is sufficiently regular, it is further shown that the resulting bound is asymptotically sharp for a large class of elliptic boundary value problems, including problems with variable and discontinuous coefficients. In particular, the analysis of typical examples shows that the convergence rate is insensitive to discontinuities under some reasonable assumptions on the aggregation scheme. Copyright © 2010 John Wiley & Sons, Ltd.     

Robust stability and H∞ control for nonlinear discrete‐time switched systems with interval time‐varying delay

This paper considers the problems of the robust stability analysis and H_∞ controller synthesis for uncertain discrete‐time switched systems with interval time‐varying delay and nonlinear disturbances. Based on the system transformation and by introducing a switched Lyapunov‐Krasovskii functional, the novel sufficient conditions, which guarantee that the uncertain discrete‐time switched system is robust asymptotically stable are obtained in terms of linear matrix inequalities. Then, the robust H_∞ control synthesis via switched state feedback is studied for a class of discrete‐time switched systems with uncertainties and nonlinear disturbances. We designed a switched state feedback controller to stabilize asymptotically discrete‐time switched systems with interval time‐varying delay and H_∞ disturbance attenuation level based on matrix inequality conditions. Examples are provided to illustrate the advantage and effectiveness of the proposed method.     

Prefiltration technique via aggregation for constructing low‐density high‐quality factorized sparse approximate inverse preconditionings

This paper considers a new approach to a priori sparsification of the sparsity pattern of the factorized approximate inverses (FSAI) preconditioner using the so‐called vector aggregation technique. The suggested approach consists in construction of the FSAI preconditioner to the aggregated matrix with a prescribed sparsity pattern. Then small entries of the computed ‘aggregated’ FSAI preconditioning matrix are dropped, and the resulting pointwise sparsity pattern is used to construct the low‐density block sparsity pattern of the FSAI preconditioning matrix to the original matrix. This approach allows to minimize (sometimes significantly) the construction costs of low‐density high‐quality FSAI preconditioners. Numerical results with sample matrices from structural mechanics and thin shell problems are presented. Copyright © 2002 John Wiley & Sons, Ltd.     

Optimal Gerschgorin‐type inclusion intervals of singular values

In this paper, some optimal inclusion intervals of matrix singular values are discussed in the set Ω_A of matrices equimodular with matrix A. These intervals can be obtained by extensions of the Gerschgorin‐type theorem for singular values, based only on the use of positive scale vectors and their intersections. Theoretic analysis and numerical examples show that upper bounds of these intervals are optimal in some cases and lower bounds may be non‐trivial (i.e. positive) when PA is a H‐matrix, where P is a permutation matrix, which improves the conjecture in Reference (Linear Algebra Appl 1984; 56 :105‐119). Copyright © 2006 John Wiley & Sons, Ltd.     

A high‐order B‐spline collocation scheme for solving a nonhomogeneous time‐fractional diffusion equation

A high‐accuracy numerical approach for a nonhomogeneous time‐fractional diffusion equation with Neumann and Dirichlet boundary conditions is described in this paper. The time‐fractional derivative is described in the sense of Riemann‐Liouville and discretized by the backward Euler scheme. A fourth‐order optimal cubic B‐spline collocation (OCBSC) method is used to discretize the space variable. The stability analysis with respect to time discretization is carried out, and it is shown that the method is unconditionally stable. Convergence analysis of the method is performed. Two numerical examples are considered to demonstrate the performance of the method and validate the theoretical results. It is shown that the proposed method is of order O(Δx⁴ + Δt^{2 ? α}) convergence, where α ∈ (0,1) . Moreover, the impact of fractional‐order derivative on the solution profile is investigated. Numerical results obtained by the present method are compared with those obtained by the method based on standard cubic B‐spline collocation method. The CPU time for present numerical method and the method based on cubic B‐spline collocation method are provided.     

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.     

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

Modeling and analysis of system reliability using phase‐type distribution closure properties

Phase‐type distribution closure properties are utilized to devise algorithms for generating reliability functions of systems with basic structures. These structures include series, parallel, K‐out‐of‐N, and standby structures with perfect/imperfect switch. The algorithms form a method for system reliability modeling and analysis based on the relationship between the system lifetime and component lifetimes for general structures. The proposed method is suitable for functional system reliability analysis, which can produce reliability functions of systems with independent components instead of only system reliability values. Once the system reliability function is obtained, other reliability measures such as the system's hazard function and mean time to failure can be obtained efficiently using only matrix algebra. Dimensional and numerical comparisons with computerized symbolic processing are also presented to show the superiority of the proposed method.     

Blended kernel approximation in the ℋ︁‐matrix techniques

Several types of ??‐matrices were shown to provide a data‐sparse approximation of non‐local (integral) operators in FEM and BEM applications. The general construction is applied to the operators with asymptotically smooth kernel function provided that the Galerkin ansatz space has a hierarchical structure. The new class of ??‐matrices is based on the so‐called blended FE and polynomial approximations of the kernel function and leads to matrix blocks with a tensor‐product of block‐Toeplitz (block‐circulant) and rank‐k matrices. This requires the translation (rotation) invariance of the kernel combined with the corresponding tensor‐product grids. The approach allows for the fast evaluation of volume/boundary integral operators with possibly non‐smooth kernels defined on canonical domains/manifolds in the FEM/BEM applications. (Here and in the following, we call domains canonical if they are obtained by translation or rotation of one of their parts, e.g. parallelepiped, cylinder, sphere, etc.) In particular, we provide the error and complexity analysis for blended expansions to the Helmholtz kernel. Copyright © 2002 John Wiley & Sons, Ltd.     

Multipliers‐free dual‐primal domain decomposition methods for nonsymmetric matrices and their numerical testing

The most commonly used nonoverlapping domain decomposition algorithms, such as the FETI‐DP and BDDC, require the introduction of discontinuous vector spaces. Most of the works on such methods are based on approaches that originated in Lagrange multipliers formulations. Using a theory of partial differential equations formulated in discontinuous piecewise‐defined functions, introduced and developed by Herrera and his collaborators through a long time span, recently the authors have developed an approach to domain decomposition methods in which general problems with prescribed jumps are treated at the discrete level. This yields an elegant and general direct framework that permits analyzing the problems in greater detail. The algorithms derived using it have properties similar to those of well‐established methods such as FETI‐DP, but, in our experience, they are easier to implement. Also, they yield explicit matrix formulas that unify the different methods. Furthermore, this multipliers‐free framework has permitted us to extend such formulas to make them applicable to nonsymmetric matrices. The extension of the unifying matrix formulas to nonsymmetric matrices is the subject matter of the present article. A conspicuous result is that in numerical experiments in 2D and 3D, the MF‐DP algorithms for nonsymmetric matrices exhibit an efficiency of the same order as state‐of‐the‐art algorithms for symmetric matrices, such as BDDC, FETI‐DP, and MF‐DP.© 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1262‐1289, 2011     

A direct method for solving block‐Toeplitz with near‐circulant‐block systems with applications to hybrid manufacturing systems

In this paper, we present a direct method for solving linear systems of a block‐Toeplitz matrix with each block being a near‐circulant matrix. The direct method is based on the fast Fourier transform (FFT) and the Sherman–Morrison–Woodbury formula. We give a cost analysis for the proposed method. The method is then applied to solve the steady‐state probability distribution of a hybrid manufacturing system which consists of a manufacturing process and a re‐manufacturing process. Copyright © 2005 John Wiley & Sons, Ltd.     

Numerical solution of nonlinear partial quadratic integro‐differential equations of fractional order via hybrid of block‐pulse and parabolic functions

In this paper, an effective numerical approach based on a new two‐dimensional hybrid of parabolic and block‐pulse functions (2D‐PBPFs) is presented for solving nonlinear partial quadratic integro‐differential equations of fractional order. Our approach is based on 2D‐PBPFs operational matrix method together with the fractional integral operator, described in the Riemann–Liouville sense. The main characteristic behind this approach is to reduce such problems to those of solving systems of algebraic equations, which greatly simplifies the problem. By using Newton's iterative method, this system is solved, and the solution of fractional nonlinear partial quadratic integro‐differential equations is achieved. Convergence analysis and an error estimate associated with the proposed method is obtained, and it is proved that the numerical convergence order of the suggested numerical method is O(h³) . The validity and applicability of the method are demonstrated by solving three numerical examples. Numerical examples are presented in the form of tables and graphs to make comparisons with the exact solutions much easier.     

Quasi‐Toeplitz splitting iteration methods for unsteady space‐fractional diffusion equations

We construct a class of quasi‐Toeplitz splitting iteration methods to solve the two‐sided unsteady space‐fractional diffusion equations with variable coefficients. By making full use of the structural characteristics of the coefficient matrix, the method only requires computational costs of O(n log n) with n denoting the number of degrees of freedom. We develop an appropriate circulant matrix to replace the Toeplitz matrix as a preconditioner. We discuss the spectral properties of the quasi‐circulant splitting preconditioned matrix. Numerical comparisons with existing approaches show that the present method is both effective and efficient when being used as matrix splitting preconditioners for Krylov subspace iteration methods.     

Solutions of symmetry‐constrained least‐squares problems

In this paper, two new matrix‐form iterative methods are presented to solve the least‐squares problem: and matrix nearness problem: where matrices and are given; ??₁ and ??₂ are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and S_XY is the solution pair set of the minimum residual problem. These new matrix‐form iterative methods have also faster convergence rate and higher accuracy than the matrix‐form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13 : 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix‐form iterative methods. Some numerical examples illustrate the efficiency of the new matrix‐form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd.     

Asymptotic behaviour of a two‐dimensional differential system with non‐constant delay

The asymptotic behaviour and stability properties are studied for a real two‐dimensional system x^′(t) = A(t)x (t) + B(t)x (θ (t)) + h (t, x (t), x (θ (t))), with a nonconstant delay t ‐ θ (t) ≥ 0. It is supposed that A,B and h are matrix functions and a vector function, respectively. The method of investigation is based on the transformation of the considered real system to one equation with complex‐valued coefficients. Stability and asymptotic properties of this equation are studied by means of a suitable Lyapunov‐Krasovskii functional. The results generalize the great part of the results of J. Kalas and L. Baráková [J. Math. Anal. Appl. 269 , No. 1, 278–300 (2002)] for two‐dimensional systems with a constant delay (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Adaptive reduction‐based AMG

With the ubiquity of large‐scale computing resources has come significant attention to practical details of fast algorithms for the numerical solution of partial differential equations. Included in this group are the class of multigrid and algebraic multigrid algorithms that are effective solvers for many of the large matrix problems arising from the discretization of elliptic operators. Algebraic multigrid (AMG) is especially effective for many problems with discontinuous coefficients, discretized on unstructured grids, or over complex geometries. While much effort has been invested in improving the practical performance of AMG, little theoretical understanding of this performance has emerged. This paper presents a two‐level convergence theory for a reduction‐based variant of AMG, called AMGr, which is particularly appropriate for linear systems that have M‐matrix‐like properties. For situations where less is known about the problem matrix, an adaptive version of AMGr that automatically determines the form of the reduction needed by the AMGr process is proposed. The adaptive cycle is shown, in both theory and practice, to yield an effective AMGr algorithm. Copyright © 2006 John Wiley & Sons, Ltd.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

On a sub‐Stiefel Procrustes problem arising in computer vision

A sub‐Stiefel matrix is a matrix that results from deleting simultaneously the last row and the last column of an orthogonal matrix. In this paper, we consider a Procrustes problem on the set of sub‐Stiefel matrices of order n. For n = 2, this problem has arisen in computer vision to solve the surface unfolding problem considered by R. Fereirra, J. Xavier and J. Costeira. An iterative algorithm for computing the solution of the sub‐Stiefel Procrustes problem for an arbitrary n is proposed, and some numerical experiments are carried out to illustrate its performance. For these purposes, we investigate the properties of sub‐Stiefel matrices. In particular, we derive two necessary and sufficient conditions for a matrix to be sub‐Stiefel. We also relate the sub‐Stiefel Procrustes problem with the Stiefel Procrustes problem and compare it with the orthogonal Procrustes problem. Copyright © 2015 John Wiley & Sons, Ltd.     

Emergent dynamics of the first‐order stochastic Cucker‐Smale model and application to finance

In this paper, we study stochastic aggregation properties of the financial model for the N‐asset price process whose dynamics is modeled by the weakly geometric Brownian motions with stochastic drifts. For the temporal evolution of stochastic components of drift coefficients, we employ a stochastic first‐order Cucker‐Smale model with additive noises. The asset price processes are weakly interacting via the stochastic components of drift coefficients. For the aggregation estimates, we use the macro‐micro decomposition of the fluctuations around the average process and show that the fluctuations around the average value satisfies a practical aggregation estimate over a time‐independent symmetric network topology so that we can control the differences of drift coefficients by tuning the coupling strength. We provide numerical examples and compare them with our analytical results. We also discuss some financial implications of our proposed model.