Out-of-band quasiseparable matrices

We study structured matrices which consist of a band part and quasiseparable parts below and upper the band. We extend algorithms known for quasiseparable matrices, i.e. for the case when the band consists of the main diagonal only, to a wider class of matrices. The matrices which we consider may be treated as an usual quasiseparable matrices with larger orders of generators. Hence one can apply the methods developed for usual quasiseparable matrices and obtain various linear complexity O(N) algorithms. However in this case the coefficients in N in the complexity estimates turns out to be quite large. In this paper we use the structure more accurately by division of the matrix into three parts in which the middle part is the band instead of diagonal as it is used for usual quasiseparable matrices. This approach allows to use better the structure of the matrix in order to improve the coefficients in N in the complexity estimates for the algorithms. This method works for algorithms which keep invariant the structure.     

On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

In this paper we design a fast new algorithm for reducing an N × N quasiseparable matrix to upper Hessenberg form via a sequence of N − 2 unitary transformations. The new reduction is especially useful when it is followed by the QR algorithm to obtain a complete set of eigenvalues of the original matrix. In particular, it is shown that in a number of cases some recently devised fast adaptations of the QR method for quasiseparable matrices can benefit from using the proposed reduction as a preprocessing step, yielding lower cost and a simplification of implementation.     

REPRINT OF: A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

A framework for polynomial preconditioners based on fast transforms I: Theory

Optimal and superoptimal approximations of a complex square matrix by polynomials in a normal basis matrix are considered. If the unitary transform associated with the eigenvectors of the basis matrix is computable using a fast algorithm, the approximations may be utilized for constructing preconditioners. Theorems describing how the parameters of the approximations could be efficiently computed are given, and for special cases earlier results by other authors are recovered. Also, optimal and superoptimal approximations for block matrices are determined, and the same type of theorems as for the point case are proved. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.     

Neville elimination for rank-structured matrices

In this paper it is shown that Neville elimination is suited to exploit the rank structure of an order-r quasiseparable matrix A∈C^n×n by providing a condensed decomposition of A as product of unit bidiagonal matrices, all together specified by O(nr) parameters, at the cost of O(nr³) flops. An application of this result for eigenvalue computation of totally positive rank-structured matrices is also presented.     

A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

Lower bounds of error estimates for singular perturbation problems with Jacobi-Spectral approximations

With weighted orthogonal Jacobi polynomials, we study spectral approximations for singular perturbation problems on an interval. The singular parameters of the model are included in the basis functions, and then its stiff matrix is diagonal. Considering the estimations for weighted orthogonal coefficients, a special technique is proposed to investigate the a posteriori error estimates. In view of the difficulty of a posteriori error estimates for spectral approximations, we employ a truncation projection to study lower bounds for the models. Specially, we present the lower bounds of a posteriori error estimates with two different weighted norms in details.     

UPGMA clustering revisited: A weight-driven approach to transitive approximation

A new algorithm is proposed for generating min-transitive approximations of a given similarity matrix (i.e. a symmetric matrix with elements in the unit interval and diagonal elements equal to one). Different approximations are generated depending on the choice of an aggregation operator that plays a central role in the algorithm. If the maximum operator is chosen, then the approximation coincides with the min-transitive closure of the given similarity matrix. In case of the arithmetic mean, a transitive approximation is generated which is, on the average, as close to the given similarity matrix as the approximation generated by the UPGMA hierarchical clustering algorithm. The new algorithm also allows to generate approximations in a purely ordinal setting. As this new approach is weight-driven, the partition tree associated to the corresponding min-transitive approximation can be built layer by layer. Numerical tests carried out on synthetic data are used for comparing different approximations generated by the new algorithm with certain approximations obtained by classical methods.     

Deterministic particle method approximation of a contact inhibition cross-diffusion problem

We use a deterministic particle method to produce numerical approximations to the solutions of an evolution cross-diffusion problem for two populations.According to the values of the diffusion parameters related to the intra- and inter-population repulsion intensities, the system may be classified in terms of an associated matrix. When the matrix is definite positive, the problem is well posed and the finite element approximation produces convergent approximations to the exact solution.A particularly important case arises when the matrix is only positive semi-definite and the initial data are segregated: the contact inhibition problem. In this case, the solutions may be discontinuous and hence the (conforming) finite element approximation may exhibit instabilities in the neighborhood of the discontinuity.In this article we deduce the particle method approximation to the general cross-diffusion problem and apply it to the contact inhibition problem. We then provide some numerical experiments comparing the results produced by the finite element and the particle method discretizations.     

Approximating posterior probabilities in a linear model with possibly noninvertible moving average errors

The method of Laplace is used to approximate posterior probabilities for a collection of polynomial regression models when the errors follow a process with a noninvertible moving average component. These results are useful in the problem of period-change analysis of variable stars and in assessing the posterior probability that a time series with trend has been overdifferenced. The nonstandard covariance structure induced by a noninvertible moving average process can invalidate the standard Laplace method. A number of analytical tools is used to produce corrected Laplace approximations. These tools include viewing the covariance matrix of the observations as tending to a differential operator. The use of such an operator and its Green's function provides a convenient and systematic method of asymptotically inverting the covariance matrix.In certain cases there are two different Laplace approximations, and the appropriate one to use depends upon unknown parameters. This problem is dealt with by using a weighted geometric mean of the candidate approximations, where the weights are completely data-based and such that, asymptotically, the correct approximation is used. The new methodology is applied to an analysis of the prototypical long-period variable star known as Mira.     

Bias of LS estimators in nonlinear regression models with constraints. Part II: Biadditive Models

General results giving approximate bias for nonlinear models with constrained parameters are applied to bilinear models in ANOVA framework, called biadditive models. Known results on the information matrix and the asymptotic variance matrix of the parameters are summarized, and the Jacobians and Hessians of the response and of the constraints are derived. These intermediate results are the basis for any subsequent second order study of the model. Despite the large number of parameters involved, bias formulae turn out to be quite simple due to the orthogonal structure of the model. In particular, the response estimators are shown to be approximately unbiased. Some simulations assess the validity of the approximations.     

On stability boundaries of conservative systems

Stability boundaries of linear conservative systems smoothly dependent on several parameters are studied. Generic singularities appearing on the stability boundaries are classified. Explicit formulae for the approximations to the stability domain at regular and singular points of the boundary are derived. These formulae use information on the system only at the point under consideration (eigenvectors and derivatives of the stiffness matrix with respect to parameters). As an example a buckling problem of a column loaded by an axial force is considered and discussed in detail.     

Chebyshev rational matrix approximation with a priori error bounds for linear and Riccati matrix equations

This paper deals with initial value problems for Lipschitz continuous coefficient matrix Riccati equations. Using Chebyshev polynomial matrix approximations the coefficients of the Riccati equation are approximated by matrix polynomials in a constructive way. Then using the Fröbenius method developed in [1], given an admissible error ϵ > 0 and the previously guaranteed existence domain, a rational matrix polynomial approximation is constructed so that the error is less than ϵ in all the existence domain. The approach is also considered for the construction of matrix polynomial approximations of nonhomogeneous linear differential systems avoiding the integration of the transition matrix of the associated homogeneous problem.     

A type of matrix Padé approximant inspired by scalar component models

In this paper we define a type of matrix Padé approximant inspired by the identification stage of multivariate time series models considering scalar component models. Of course, the formalization of certain properties in the matrix Padé approximation framework can be applied to time series models and in other fields. Specifically, we want to study matrix Padé approximants as follows: to find rational representations (or rational approximations) of a matrix formal power series, with both matrix polynomials, numerator and denominator, satisfying three conditions: (a) minimum row degrees for the numerator and denominator, (b) an invertible denominator at the origin, and (c) canonical representation (without free parameters).     

Methods of the secant type for systems of equations with symmetric jacobian matrix

Symmetric methods (SS methods) of the secant type are proposed for systems of equations with symmetric Jacobian matrix. The SSI and SS2 methods generate sequences of symmetric matrices J and H which approximate the Jacobian matrix and inverse one, respectively. Rank-two quasi-Newton formulas for updating J and H are derived. The structure of the approximations J and H is better than the structure of the corresponding approximations in the traditional secant method because the SS methods take into account symmetry of the Jacobian matrix. Furthermore, the new methods retain the main properties of the traditional secant method, namely, J and H are consistent approximations to the Jacobian matrix; the SS methods converge superlinearly; the sequential (n + 1)-point SS methods have the R-order at least equal to the positive root of t_n+1-1=0.     

Robust low-rank data matrix approximations

We review some recent approaches to robust approximations of low-rank data matrices. We consider the problem of estimating a low-rank mean matrix when the data matrix is subject to measurement errors as well as gross outliers in some of its entries. The purpose of the paper is to make various algorithms accessible with an understanding of their abilities and limitations to perform robust low-rank matrix approximations in both low and high dimensional problems.     

Magnus integrators for solving linear-quadratic differential games

We consider Magnus integrators to solve linear-quadratic N$N$-player differential games. These problems require to solve, backward in time, non-autonomous matrix Riccati differential equations which are coupled with the linear differential equations for the dynamic state of the game, to be integrated forward in time. We analyze different Magnus integrators which can provide either analytical or numerical approximations to the equations. They can be considered as time-averaging methods and frequently are used as exponential integrators. We show that they preserve some of the most relevant qualitative properties of the solution for the matrix Riccati differential equations as well as for the remaining equations. The analytical approximations allow us to study the problem in terms of the parameters involved. Some numerical examples are also considered which show that exponential methods are, in general, superior to standard methods.     

The inertia of the symmetric approximation for low-rank matrices

In many areas of applied linear algebra, it is necessary to work with matrix approximations. A usual situation occurs when a matrix obtained from experimental or simulated data is needed to be approximated by a matrix that lies in a corresponding statistical model and satisfies some specific properties. In this short note, we focus on symmetric and positive-semidefinite approximations and we show that the positive and negative indices of inertia of the symmetric approximation and the rank of the positive-semidefinite approximation are always bounded from above by the rank of the original matrix.     

Bounds on the error of an approximate invariant subspace for non-self-adjoint matrices

Summary. Suppose one approximates an invariant subspace of an matrix in which in not necessarily self--adjoint. Suppose that one also has an approximation for the corresponding eigenvalues. We consider the question of how good the approximations are. Specifically, we develop bounds on the angle between the approximating subspace and the invariant subspace itself. These bounds are functions of the following three terms: (1) the residual of the approximations; (2) singular--value separation in an associated matrix; and (3) the goodness of the approximations to the eigenvalues. Received December 1, 1992 / Revised version received October 20, 1993