On vandermonde systems solution in the symmetric case

Vandermonde matrices defined by pairs of symmetric points with respect to the origin are analysed. Direct methods for the determinant computation and for the linear system solution, both for primal and dual case, are proposed that reduce the computational complexity by a factor four and two respectively with respect to the known algorithms of ordern ². Moreover perturbation bounds for the new LUD factorization error are found depending on a condition number of an halved dimension Vandermonde matrix.

---

Sunto Si considerano matrici di Vandermonde definite da coppie di punti simmetrici rispetto all'origine. Sono proposti metodi diretti per il calcolo del determinante e per la soluzione dei sistemi lineari, sia nel caso primario che duale, che riducono rispettivamente di un fattore quattro e due la complessità computazionale degli algoritmi noti di ordinen ². Inoltre si determinano limitazioni dell'errore della nuova fattorizzazione LUD dipendenti dall'indice di condizionamento di una matrice di Vandermonde di dimensioni dimezzate.

     

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.     

Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

In this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log²n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given.     

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Due to their remarkable application in many branches of applied mathematics such as combinatorics, coding theory, and cryptography, Vandermonde matrices have received a great amount of attention. Maximum distance separable (MDS) codes introduce MDS matrices which not only have applications in coding theory but also are of great importance in the design of block ciphers. Lacan and Fimes introduce a method for the construction of an MDS matrix from two Vandermonde matrices in the finite field. In this paper, we first suggest a method that makes an involutory MDS matrix from the Vandermonde matrices. Then we propose another method for the construction of 2 ⁿ × 2 ⁿ Hadamard MDS matrices in the finite field GF(2 ^q ). In addition to introducing this method, we present a direct method for the inversion of a special class of 2 ⁿ ?× 2 ⁿ Vandermonde matrices.     

Approximations with Real Linear Modules

Real linear approximation theory is developed further by regarding ? ⁿ as a module over the ring of circlets. By introducing a concept of orthogonality together with the respective Gram–Schmidt orthogonalization process, improved approximations upon the standard complex Hilbert space techniques follow. Related hierarchical bases are devised leading to a new family of rapidly constructible family of unitary matrices. With circlets, so-called oplets are introduced for approximation to improve the singular value decomposition of real matrices. Complex matrix approximation is also considered through finding the nearest real matrix in small rank perturbations.     

A family of identities related to zero-sum and team games

We list and prove a family of binomial identities by calculating in two ways the probabilities of approximate saddlepoints occurring in random m×n matrices. The identities are easily seen to be equivalent to the evaluation of a family of Gauss ₂F₁ polynomials according to a formula of Vandermonde. We also consider some implications concerning the number of approximate pure strategy Nash equilibria we can expect in large matrix zero-sum and team games.     

Displacement structure approach to q-adic Chebyshev–Vandermonde-like matrices

In this paper, a new class of so-called q-adic Chebyshev–Vandermonde-like matrices over an arbitrary non-algebraically closed field is introduced. This class generalizes both the ordinary Chebyshev–Vandermonde-like matrices over the complex field studied earlier by Kailath and Olshevsky [T. Kailath, V. Olshevsky, Displacement structure approach to Chebyshev–Vandermonde and related matrices, Integral Equations Operator Theory 22 (1995) 65–92], and the classical q-adic Vandermonde-like matrices with respect to power basis by Yang and Hu [Z.H. Yang, Y.J. Hu, Displacement structure and fast inversion formulas for q-adic Vandermonde-like matrices, J. Comput. Appl. Math. 176 (2005) 1–14]. Three kinds of displacement structures and consequently, three kinds of fast inversion formulas are presented for this class of matrices by using displacement structure theory method, which generalize the corresponding results for Chebyshev–Vandermonde-like and q-adic Vandermonde-like matrices.     

Gaps in the base set of primitive nonpowerful sign patterns

For a primitive nonpowerful square sign pattern A, the base of A, denoted by l(A), is the least positive integer l such that every entry of A ^l is #. In this article, we consider the base set of the primitive nonpowerful sign pattern matrices. Some useful results about the bases for the sign pattern matrices are presented there. Some special sign pattern matrices with given bases are characterized and more ‘gaps’ in the base set are shown.     

Efficient Computation of Analytic Bases in Evans Function Analysis of Large Systems

In Evans function computations of the spectra of asymptotically constant-coefficient linearized operators of large systems, a problem that becomes important is the efficient computation of global analytically varying bases for invariant subspaces of the limiting coefficient matrices. In the case that the invariant subspace is spectrally separated from its complementary invariant subspace, we propose an efficient numerical implementation of a standard projection-based algorithm of Kato, for which the key step is the solution of an associated Sylvester problem. This may be recognized as the analytic cousin of a C ^k algorithm developed by Dieci and collaborators based on orthogonal projection rather than eigenprojection as in our case. For a one-dimensional subspace, it reduces essentially to an algorithm of Bridges, Derks and Gottwald based on path-finding and continuation methods.     

Complexity reduction of least squares problems involving special vandermonde matrices

This paper presents a new QRD factorization of a rectangular Vandermonde matrix for a special point distribution, including the symmetric case, based on ak-dimensional block decomposition of the matrix and some properties of the Kronecker product. The computational reduction factor with respect to any QR method isk ², in the general case, and 4 in the symmetric one. By the resulting matrix factorization, new formulas are devised for the least squares system solution, whose implementation produces an algorithm of reduced computational cost and computer storage. Finally the perturbation bounds of this new factorization are devised.     

Base tensorielle des matrices de Hankel (ou de Toeplitz) Applications

Summary The set of all Hankel (or Toeplitz) matrices of dimensionn, is shown to possess tensorial bases: bases made ofn rank one matrices. Four families of such tensorial bases are possible. From this result, we deduce that the following computations can be performed with a number of multiplications of ordern instead of ordern ²: evaluation of the 2n+1 coefficients of the polynomial product of two polynomials of degreen, evaluation of the inverse of a lower triangular toeplitz matrix, evaluation of the quotient and of the remainder in the division of a polynomial of degree 2n by a polynomial of degreen.     

Frame Wavelets with Compact Supports for L^2（R^n）

The construction of frame wavelets with compact supports is a meaningful problem in wavelet analysis. In particular, it is a hard work to construct the frame wavelets with explicit analytic forms. For a given n × n real expansive matrix A, the frame-sets with respect to A are a family of sets in R^n. Based on the frame-sets, a class of high-dimensional frame wavelets with analytic forms are constructed, which can be non-bandlimited, or even compactly supported. As an application, the construction is illustrated by several examples, in which some new frame wavelets with compact supports are constructed. Moreover, since the main result of this paper is about general dilation matrices, in the examples we present a family of frame wavelets associated with some non-integer dilation matrices that is meaningful in computational geometry.     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

On the evaluation of some Selberg-like integrals

Several methods of evaluation are presented for a family {In,d,p} of Selberg-like integrals that arise in the computation of the algebraic-geometric degrees of a family of spherical nilpotent orbits associated to the symmetric space of a simple real Lie group. Adapting the technique of Nishiyama, Ochiai and Zhu, we present an explicit evaluation in terms of certain iterated sums over permutation groups. The resulting formula, however, is only valid when the integrand involves an even power of the Vandermonde determinant. We then apply, to the general case, the theory of symmetric functions and obtain an evaluation of the integral In,d,p as a product of polynomial of fixed degree times a particular product of gamma factors; thereby identifying the asymptotics of the integrals with respect to their parameters. Lastly, we derive a recursive formula for evaluation of another general class of Selberg-like integrals, by applying some of the technology of generalized hypergeometric functions.     

On Identity Bases of Exclusion Varieties for Monoids

An exclusion variety is a variety that is maximal with respect to not containing some semigroup. It is shown that if the bases of all exclusion varieties for some periodic semigroup S are known, then the bases of exclusion varieties for the monoid S ¹ can be computed.     

Optimally scaled and optimally conditioned Vandermonde and Vandermonde-like matrices

Vandermonde matrices with real nodes are known to be severely ill-conditioned. We investigate numerically the extent to which the condition number of such matrices can be reduced, either by row-scaling or by optimal configurations of nodes. In the latter case we find empirically the condition of the optimally conditioned n×n Vandermonde matrix to grow exponentially at a rate slightly less than \((1+\sqrt{2})^{n}\). Much slower growth—essentially linear—is observed for optimally conditioned Vandermonde-Jacobi matrices. We also comment on the computational challenges involved in determining condition numbers of highly ill-conditioned matrices.     

Function of a square matrix with repeated eigenvalues

An analytical function f(A) of an arbitrary n×n constant matrix A is determined and expressed by the “fundamental formula”, the linear combination of constituent matrices. The constituent matrices Z_kh, which depend on A but not on the function f(s), are computed from the given matrix A, that may have repeated eigenvalues. The associated companion matrix C and Jordan matrix J are then expressed when all the eigenvalues with multiplicities are known. Several other related matrices, such as Vandermonde matrix V, modal matrix W, Krylov matrix K and their inverses, are also derived and depicted as in a 2-D or 3-D mapping diagram. The constituent matrices Z_kh of A are thus obtained by these matrices through similarity matrix transformations. Alternatively, efficient and direct approaches for Z_kh can be found by the linear combination of matrices, that may be further simplified by writing them in “super column matrix” forms. Finally, a typical example is provided to show the merit of several approaches for the constituent matrices of a given matrix A.     

A heuristic for decomposing traffic matrices in TDMA satellite communication

A heuristic for decomposing traffic matrices in TDMA satellite communication. With the time-division multiple access (TDMA) technique in satellite communication the problem arises to decompose a givenn×n traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large asn ². When the number of matrices is restricted ton, the problem is NP-hard. In this paper we propose a heuristic based on a scaling technique which for each number of allowed matrices in the range fromn ton ² allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristic methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.This work was supported by the Fonds zur Förderung der wissenschaftlichen Forschung, Project S32/01.     

Piecewise Linear Bases and Besov Spaces on Fractal Sets

For a class of closed sets F R ⁿ admitting a regular sequence of triangulations or generalized triangulations, the analogues on F of the Faber—Schauder and Franklin bases are discussed. The characterizations of the Besov spaces on F in the terms of coefficients of functions with respect to these bases are proved. As a consequence, analogous characterizations of the Besov spaces on some fractal domains (including the Sierpinski gasket and the von Koch curve) by coefficients of functions with respect to the wavelet bases constructed in [26] are obtained.