New Tchebyshev‐Galerkin operational matrix method for solving linear and nonlinear hyperbolic telegraph type equations

The telegraph equation describes various phenomena in many applied sciences. We propose two new efficient spectral algorithms for handling this equation. The principal idea behind these algorithms is to convert the linear/nonlinear telegraph problems (with their initial and boundary conditions) into a system of linear/nonlinear equations in the expansion coefficients, which can be efficiently solved. The main advantage of our algorithm in the linear case is that the resulting linear systems have special structures that reduce the computational effort required for solving them. The numerical algorithms are supported by a careful convergence analysis for the suggested Chebyshev expansion. Some illustrative examples are given to demonstrate the wide applicability and high accuracy of the proposed algorithms. © 2016Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1553–1571, 2016     

由三个特殊次序向量对构造三对角对称矩阵

讨论利用给定的三个特殊次序向量对构造不可约三对角矩阵、Jacobi矩阵和负Jacobi矩阵的反问题.在求解方法中,将已知的一些关系式等价地转化为线性方程组,利用线性方程组有解的条件,得到了所研究问题有惟一解的充要条件,并给出了数值算法和例子.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

A unified analysis of linear quaternion dynamic equations on time scales

Over the last years, considerable attention has been paid to the role of the quaternion differential equations (QDEs) which extend the ordinary differential equations. The theory of QDEs was recently well established and has wide applications in physics and life science. This paper establishes a systematic frame work for the theory of linear quaternion dynamic equations on time scales (QDETS), which can be applied to wave phenomena modeling, fluid dynamics and filter design. The algebraic structure of the solutions to the QDETS is actually a left- or right- module, not a linear vector space. On the non-commutativity of the quaternion algebra, many concepts and properties of the classical dynamic equations on time scales (DETS) can not be applied. They should be redefined accordingly. Using $q$-determinant, a novel definition of Wronskian is introduced under the framework of quaternions which is different from the standard one in DETS. Liouville formula for QDETS is also analyzed. Upon these, the solutions to the linear QDETS are established. The Putzer''s algorithms to evaluate the fundamental solution matrix for homogeneous QDETS are presented. Furthermore, the variation of constants formula to solve the nonhomogeneous QDETs is given. Some concrete examples are provided to illustrate the feasibility of the proposed algorithms.     

Toeplitz方程组极小范数最小二乘解的快速算法

给出了求以m×n阶Toeplitz矩阵为系数阵的线性方程组极小范数最小二乘解的快速算法.     

LMI Approximations for the Radius of the Intersection of Ellipsoids: Survey

This paper surveys various linear matrix inequality relaxation techniques for evaluating the maximum norm vector within the intersection of several ellipsoids. This difficult nonconvex optimization problem arises frequently in robust control synthesis. Two randomized algorithms and several ellipsoidal approximations are described. Guaranteed approximation bounds are derived in order to evaluate the quality of these relaxations.     

A new augmented Lyapunov-Krasovskii functional approach for stability of linear systems with time-varying delays

This paper proposes improved delay-dependent conditions for asymptotic stability of linear systems with time-varying delays. The proposed method employs a suitable Lyapunov-Krasovskii’s functional for new augmented system. Based on Lyapunov method, delay-dependent stability criteria for the systems are established in terms of linear matrix inequalities (LMIs) which can be easily solved by various optimization algorithms. Three numerical examples are included to show that the proposed method is effective and can provide less conservative results.     

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Least squares solution with the minimum-norm to general matrix equations via iteration

Two iterative algorithms are presented in this paper to solve the minimal norm least squares solution to a general linear matrix equations including the well-known Sylvester matrix equation and Lyapunov matrix equation as special cases. The first algorithm is based on the gradient based searching principle and the other one can be viewed as its dual form. Necessary and sufficient conditions for the step sizes in these two algorithms are proposed to guarantee the convergence of the algorithms for arbitrary initial conditions. Sufficient condition that is easy to compute is also given. Moreover, two methods are proposed to choose the optimal step sizes such that the convergence speeds of the algorithms are maximized. Between these two methods, the first one is to minimize the spectral radius of the iteration matrix and explicit expression for the optimal step size is obtained. The second method is to minimize the square sum of the F-norm of the error matrices produced by the algorithm and it is shown that the optimal step size exits uniquely and lies in an interval. Several numerical examples are given to illustrate the efficiency of the proposed approach.     

在两循环矩阵类中求解线性方程组反问题的快速算法

本文利用多项式最大公因式 ,给出了线性方程组的反问题在 r-循环矩阵类和对称 r-循环矩阵类中有唯一解的充要条件 ,进而得到线性方程组在 r循环矩阵类和对称 r-循环矩阵类中的反问题求唯一解的算法 .最后给出了应用该算法的数值例子 .     

Shadow block iteration for solving linear systems obtained from wavelet transforms

Matrices resulting from wavelet transforms have a special “shadow” block structure, that is, their small upper left blocks contain their lower frequency information. Numerical solutions of linear systems with such matrices require special care. We propose shadow block iterative methods for solving linear systems of this type. Convergence analysis for these algorithms are presented. We apply the algorithms to three applications: linear systems arising in the classical regularization with a single parameter for the signal de-blurring problem, multilevel regularization with multiple parameters for the same problem and the Galerkin method of solving differential equations. We also demonstrate the efficiency of these algorithms by numerical examples in these applications.     

The efficient evaluation of the hypergeometric function of a matrix argument

We present new algorithms that efficiently approximate the hypergeometric function of a matrix argument through its expansion as a series of Jack functions. Our algorithms exploit the combinatorial properties of the Jack function, and have complexity that is only linear in the size of the matrix.

     

Deconvolution and Regularization with Toeplitz Matrices

By deconvolution we mean the solution of a linear first-kind integral equation with a convolution-type kernel, i.e., a kernel that depends only on the difference between the two independent variables. Deconvolution problems are special cases of linear first-kind Fredholm integral equations, whose treatment requires the use of regularization methods. The corresponding computational problem takes the form of structured matrix problem with a Toeplitz or block Toeplitz coefficient matrix. The aim of this paper is to present a tutorial survey of numerical algorithms for the practical treatment of these discretized deconvolution problems, with emphasis on methods that take the special structure of the matrix into account. Wherever possible, analogies to classical DFT-based deconvolution problems are drawn. Among other things, we present direct methods for regularization with Toeplitz matrices, and we show how Toeplitz matrix–vector products are computed by means of FFT, being useful in iterative methods. We also introduce the Kronecker product and show how it is used in the discretization and solution of 2-D deconvolution problems whose variables separate.     

Asymptotic Stability of Neutral Systems with Multiple Delays

In this paper, the stability analysis problem for linear neutral delay-differential systems with multiple time delays is investigated. Using the Lyapunov method, we present new sufficient conditions for the asymptotic stability of systems in terms of linear matrix inequalities, which can be solved easily by various convex optimization algorithms. Numerical examples are given to illustrate the application of the proposed method.     

Implementation of sparse matrix algorithms in an advection-diffusion-chemistry module

A two-dimensional advection-diffusion-chemistry module of a large-scale environmental model is taken. The module is described mathematically by a system of partial differential equations. Sequential splitting is used in the numerical treatment. The non-linear chemistry is most time-consuming part and it is handled by six implicit algorithms for solving ordinary differential equations. This leads to the solution of very long sequences of systems of linear algebraic equations. It is crucial to solve these systems efficiently. This is achieved by applying four different algorithms. The numerical results indicate that the algorithms based on a preconditioned sparse matrix technique and on a specially designed algorithm for the particular problem under consideration perform best.     

Efficient spectral ultraspherical-Galerkin algorithms for the direct solution of 2nth-order linear differential equations

Some efficient and accurate algorithms based on the ultraspherical-Galerkin method are developed and implemented for solving 2nth-order linear differential equations in one variable subject to homogeneous and nonhomogeneous boundary conditions using a spectral discretization. We extend the proposed algorithms to solve the two-dimensional 2nth-order differential equations. The key to the efficiency of these algorithms is to construct appropriate base functions, which lead to linear systems with specially structured matrices that can be efficiently inverted, hence greatly reducing the cost and roundoff errors.     

On a class of interior point algorithms

A family of interior point algorithms for solving linear programs is examined. Under the assumption on the nondegeneracy of the problem, a theoretical justification of these algorithms is given. The sets of the algorithms converging to relatively interior optimal solutions and having linear or superlinear convergence rate are identified.     

On the inverse of certain patterned sums of matrices with Kronecker product structures

In this article, we derive explicit expressions for the entries of the inverse of a patterned matrix that is a sum of Kronecker products. This matrix keeps the Kronecker structure under matrix inversion, and it is used, for example, in statistics, in particular in the linear mixed model analysis. The obtained results present new and extended existing algorithms for the inversion of the considered patterned matrices. We also obtain a closed-form inverse in terms of block matrices.     

范德蒙型方程组最小二乘解的快速算法

在用多项式进行曲线拟合等实际问题中,需要求解以范德蒙型矩阵VT为系数阵的线性方程组VTx=b的最小二乘解.     

Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C

Fast algorithms for enclosing the minimum norm least squares solution of the matrix equation AXB = C are proposed. To develop these algorithms, theories for obtaining error bounds of numerical solutions are established. The error bounds obtained by these algorithms are verified in the sense that all the possible rounding errors have been taken into account. Techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd.