Approximating classes of sequences: The Hermitian case

Given a sequence {A_n} of matrices A_n of increasing dimension d_n with d_k>d_q for k>q, k,q∈N, we recently introduced the concept of approximating class of sequences (a.c.s.) in order to define a basic approximation theory for matrix sequences. We have shown that such a notion is stable under inversion, linear combinations, and product, whenever natural and mild conditions are satisfied. In this note we focus our attention on the Hermitian case and we show that is an a.c.s. for {f(A_n)}, if is an a.c.s. for {A_n}, {A_n} is sparsely unbounded, and f is a suitable continuous function defined on R. We also discuss the potential impact and future developments of such a result.     

Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension

In the present paper we present the tensor-product approximation of a multidimensional convolution transform discretized via a collocation-projection scheme on uniform or composite refined grids. Examples of convolving kernels are provided by the classical Newton, Slater (exponential) and Yukawa potentials, 1/‖x‖, and with x∈R^d. For piecewise constant elements on the uniform grid of size n^d, we prove quadratic convergence O(h²) in the mesh parameter h=1/n, and then justify the Richardson extrapolation method on a sequence of grids that improves the order of approximation up to O(h³). A fast algorithm of complexity O(dR₁R₂nlogn) is described for tensor-product convolution on uniform/composite grids of size n^d, where R₁,R₂ are tensor ranks of convolving functions. We also present the tensor-product convolution scheme in the two-level Tucker canonical format and discuss the consequent rank reduction strategy. Finally, we give numerical illustrations confirming: (a) the approximation theory for convolution schemes of order O(h²) and O(h³); (b) linear-logarithmic scaling of 1D discrete convolution on composite grids; (c) linear-logarithmic scaling in n of our tensor-product convolution method on an n×n×n grid in the range n≤16384.     

Determination of a matrix function using the divided difference method of Newton and the interpolation technique of Hermite

Computing a function f(A) of an n-by-n matrix A is a frequently occurring problem in control theory and other applications. In this paper we introduce an effective approach for the determination of matrix function f(A). We propose a new technique which is based on the extension of Newton divided difference and the interpolation technique of Hermite and using the eigenvalues of the given matrix A. The new algorithm is tested on several problems to show the efficiency of the presented method. Finally, the application of this method in control theory is highlighted.     

A power penalty method for linear complementarity problems

We propose a power penalty approach to a linear complementarity problem (LCP) in Rⁿ based on approximating the LCP by a nonlinear equation. We prove that the solution to this equation converges to that of the LCP at an exponential rate when the penalty parameter tends to infinity.     

The generalized superoptimal preconditioner

For any given n-by-n matrix A, a specific circulant preconditioner t_F(A) introduced by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459-473] is defined to be the solution of

     

The principle of extrapolation and the Cayley Transform

The Cayley Transform, F:=(I+A)^-1(I-A), with A∈C^n,n and -1∉σ(A), where σ(·) denotes spectrum, is of significant theoretical importance and interest and has many practical applications. E.g., in the solution of the Linear Complementarity Problem (LCP), in the solution of linear systems arising from the discretization of model problems elliptic PDEs by Alternating Direction Implicit (ADI) iterative methods, in the solution of complex linear systems by ADI-type methods of Hermitian/Skew Hermitian or Normal/Skew Hermitian Splittings, etc. In the present work we apply the principle of Extrapolation to generalize the Cayley Transform and determine in an optimal sense the extrapolation parameter involved so that problems in many practical applications are solved much more efficiently.     

Solving the generalized regularized long wave equation on the basis of a reproducing kernel space

On the basis of a reproducing kernel space, an iterative algorithm for solving the generalized regularized long wave equation is presented. The analytical solution in the reproducing kernel space is shown in a series form and the approximate solution u_n is constructed by truncating the series to n terms. The convergence of u_n to the analytical solution is also proved. Results obtained by the proposed method imply that it can be considered as a simple and accurate method for solving such evolution equations.     

On the root closedness of continuous function algebras

For a compact Hausdorff space X, C(X) denotes the algebra of all complex-valued continuous functions on X. For a positive integer n, we say that C(X) is n-th root closed if, for each f∈C(X), there exists g∈C(X) such that f=gn. It is shown that, for each integer m?2, there exists a compact Hausdorff space Xm such that C(Xm) is m-th root closed, but not n-th root closed for each integer n relatively prime to m. This answers a question posed by Countryman Jr. [R.S. Countryman Jr., On the characterization of compact Hausdorff X for which C(X) is algebraically closed, Pacific J. Math. 20 (1967) 433-438] et al.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Circulant preconditioners for pricing options

We use the normalized preconditioned conjugate gradient method with Strang’s circulant preconditioner to solve a nonsymmetric Toeplitz system A_nx=b, which arises from the discretization of a partial integro-differential equation in option pricing. By using the definition of family of generating functions introduced in [16], we prove that Strang’s circulant preconditioner leads to a superlinear convergence rate under certain conditions. Numerical results exemplify our theoretical analysis.     

Factors of binomial sums from the Catalan triangle

By using the Newton interpolation formula, we generalize the recent identities on the Catalan triangle obtained by Miana and Romero as well as those of Chen and Chu. We further study divisibility properties of sums of products of binomial coefficients and an odd power of a natural number. For example, we prove that for all positive integers n₁,…,nm, nm+1=n₁, and any nonnegative integer r, the expression

     

Some properties of generalized K-centrosymmetric H-matrices

Every n×n$n\times n$ generalized K-centrosymmetric matrix A   can be reduced into a 2×2$2\times 2$ block diagonal matrix (see [Z. Liu, H. Cao, H. Chen, A note on computing matrix–vector products with generalized centrosymmetric (centrohermitian) matrices, Appl. Math. Comput. 169 (2) (2005) 1332–1345]). This block diagonal matrix is called the reduced form of the matrix A. In this paper we further investigate some properties of the reduced form of these matrices and discuss the square roots of these matrices. Finally exploiting these properties, the development of structure-preserving algorithms for certain computations for generalized K-centrosymmetric H-matrices is discussed.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

Displacement structure approach to Chebyshev-Vandermonde and related matrices

In this paper we use the displacement structure concept to introduce a new class of matrices, designated asChebyshev-Vandermonde-like matrices, generalizing ordinary Chebyshev-Vandermonde matrices, studied earlier by different authors. Among other results the displacement structure approach allows us to give a nice explanation for the form of the Gohberg-Olshevsky formulas for the inverses of ordinary Chebyshev-Vandermonde matrices. Furthermore, the fact that the displacement structure is inherited by Schur complements leads to a fastO(n ²) implementation of Gaussian elimination withpartial pivoting for Chebyshev-Vandermonde-like matrices.     

Hartley preconditioners for Toeplitz systems generated by positive continuous functions

In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT _n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM _n is defined to be the minimizer of T _n –B _{n F} over allB _n H _n whereH _n is the Hartley algebra. We show that if the generating functionf ofT _n is a positive 2-periodic continuous even function, then the spectrum of the preconditioned systemM _n ^–1 T _n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Extension dimension and quasi-finite CW-complexes

We extend the definition of quasi-finite complexes from countable complexes to arbitrary ones and provide a characterization of quasi-finite complexes in terms of L-invertible maps and dimensional properties of compactifications. Several results related to the class of quasi-finite complexes are established, such as completion of metrizable spaces, existence of universal spaces and a version of the factorization theorem. Furthermore, we define UV(L)-spaces in the realm of metrizable spaces and show that some properties of UV(n)-spaces and UV(n)-maps remain valid for UV(L)-spaces and UV(L)-maps, respectively.     

Tensor ranks for the inversion of tensor-product binomials

The main result reads: if a nonsingular matrix A of order n=pq is a tensor-product binomial with two factors then the tensor rank of A⁻¹ is bounded from above by min{p,q}. The estimate is sharp, and in the worst case it amounts to .