Berlekamp—Massey Algorithm, Continued Fractions, Pade Approximations, and Orthogonal Polynomials

The Berlekamp—Massey algorithm (further, the BMA) is interpreted as an algorithm for constructing Pade approximations to the Laurent series over an arbitrary field with singularity at infinity. It is shown that the BMA is an iterative procedure for constructing the sequence of polynomials orthogonal to the corresponding space of polynomials with respect to the inner product determined by the given series. The BMA is used to expand the exponential in continued fractions and calculate its Pade approximations.     

Subcoalgebras and endomorphisms of free Hopf algebras

For a matrix coalgebra C over some field, we determine all small subcoalgebras of the free Hopf algebra on C, the free Hopf algebra with a bijective antipode on C, and the free Hopf algebra with antipode S satisfying on C for some fixed d. We use this information to find the endomorphisms of these free Hopf algebras, and to determine the centers of the categories of Hopf algebras, Hopf algebras with bijective antipode, and Hopf algebras with antipode of order dividing 2d.     

A continued fraction algorithm

Summary Two existing algorithms for the evaluation of a finite sequence of convergents of a continued fraction are considered. Each method has a drawback concerning numerical stability or computational effort. A third algorithm is presented which requires less computations than the first method, and generally is more stable than the second one. The results are illustrated by numerical examples. The connection with Mikloko's algorithm is shown.     

Fibrant extensions of free G-spaces

We show that any equivariant fibrant extension of a compact free G-space is also free. This result allows us to prove that the orbit space of any equivariant fibrant compact space E is also fibrant, provided that E has only one orbit type.     

Gröbner-Shirshov bases for associative algebras with multiple operators and free Rota-Baxter algebras

In this paper, we establish the Composition-Diamond lemma for associative algebras with multiple linear operators. As applications, we obtain Gröbner-Shirshov bases of free Rota-Baxter algebra, free λ-differential algebra and free λ-differential Rota-Baxter algebra, respectively. In particular, linear bases of these three free algebras are respectively obtained, which are essentially the same or similar to the recent results obtained by K. Ebrahimi-Fard-L. Guo, and L. Guo-W. Keigher by using other methods.     

Matrix pencils completion problems

In this paper we give a partial solution to the challenge problem posed by Loiseau et al. in [J. Loiseau, S. Mondié, I. Zaballa, P. Zagalak, Assigning the Kronecker invariants of a matrix pencil by row or column completion, Linear Algebra Appl. 278 (1998) 327-336], i.e. we assign the Kronecker invariants of a matrix pencil obtained by row or column completion. We have solved this problem over arbitrary fields.     

A quaternion QR algorithm

Summary This paper extends the Francis QR algorithm to quaternion and antiquaternion matrices. It calculates a quaternion version of the Schur decomposition using quaternion unitary similarity transformations. Following a finite step reduction to a Hessenberg-like condensed form, a sequence of implicit QR steps reduces the matrix to triangular form. Eigenvalues may be read off the diagonal. Eigenvectors may be obtained from simple back substitutions. For serial computation, the algorithm uses only half the work and storage of the unstructured Francis QR iteration. By preserving quaternion structure, the algorithm calculates the eigenvalues of a nearby quaternion matrix despite rounding errors.     

A fast algorithm for the recursive calculation of dominant singular subspaces

In many engineering applications it is required to compute the dominant subspace of a matrix A   of dimension m×n$m\times n$, with m?n$m?n$. Often the matrix A is produced incrementally, so all the columns are not available simultaneously. This problem arises, e.g., in image processing, where each column of the matrix A represents an image of a given sequence leading to a singular value decomposition-based compression [S. Chandrasekaran, B.S. Manjunath, Y.F. Wang, J. Winkeler, H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Process. 59 (5) (1997) 321–332]. Furthermore, the so-called proper orthogonal decomposition approximation uses the left dominant subspace of a matrix A where a column consists of a time instance of the solution of an evolution equation, e.g., the flow field from a fluid dynamics simulation. Since these flow fields tend to be very large, only a small number can be stored efficiently during the simulation, and therefore an incremental approach is useful [P. Van Dooren, Gramian based model reduction of large-scale dynamical systems, in: Numerical Analysis 1999, Chapman & Hall, CRC Press, London, Boca Raton, FL, 2000, pp. 231–247].     

An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems

Summary. We discuss an inverse-free, highly parallel, spectral divide and conquer algorithm. It can compute either an invariant subspace of a nonsymmetric matrix , or a pair of left and right deflating subspaces of a regular matrix pencil . This algorithm is based on earlier ones of Bulgakov, Godunov and Malyshev, but improves on them in several ways. This algorithm only uses easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition, but not matrix inversion. Similar parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which requires matrix inversion and is faster but can be less stable than the new algorithm. Received September 20, 1994 / Revised version received February 5, 1996     

A Jacobi eigenreduction algorithm for definite matrix pairs

Summary We propose a Jacobi eigenreduction algorithm for symmetric definite matrix pairsA, J of small to medium-size real symmetric matrices withJ ²=I,J diagonal (neitherJ norA itself need be definite). Our Jacobi reduction works only on one matrix and usesJ-orthogonal elementary congruences which include both trigonometric and hyperbolic rotations and preserve the symmetry throughout the process. For the rotation parameters only the pivotal elements of the current matrix are needed which facilitates parallelization. We prove the global convergence of the method; the quadratic convergence was observed in all experiments. We apply our method in two situations: (i) eigenreducing a single real symmetric matrix and (ii) eigenreducing an overdamped quadratic matrix pencil. In both cases our method is preceded by a symmetric indefinite decomposition and performed in its one-sided variant on the thus obtained factors. Our method outdoes the standard methods like standard Jacobi orqr/ql in accuracy in spite of the use of hyperbolic transformations which are not orthogonal (a theoretical justification of this behaviour is made elsewhere). The accuracy advantage of our method can be particularly drastic if the eigenvalues are of different order. In addition, in working with quadratic pencils our method is shown to either converge or to detect non-overdampedness.     

A real algorithm for the Hermitian eigenvalue decomposition

Modifying complex plane rotations, we derive a new Jacobi-type algorithm for the Hermitian eigendecomposition, which uses only real arithmetic. When the fast-scaled rotations are incorporated, the new algorithm brings a substantial reduction in computational costs. The new method has the same convergence properties and parallelism as the symmetric Jacobi algorithm. Computational test results show that it produces accurate eigenvalues and eigenvectors and achieves great reduction in computational time.The work of this author was supported in part by the National Science Foundation grant CCR-8813493 and by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.The work of this author was supported in part by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.     

A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity

A restarted Arnoldi algorithm is given that computes eigenvalues and eigenvectors. It is related to implicitly restarted Arnoldi, but has a simpler restarting approach. Harmonic and regular Rayleigh-Ritz versions are possible.For multiple eigenvalues, an approach is proposed that first computes eigenvalues with the new harmonic restarted Arnoldi algorithm, then uses random restarts to determine multiplicity. This avoids the need for a block method or for relying on roundoff error to produce the multiple copies.     

Equations ax = c and xb = d in rings and rings with involution with applications to Hilbert space operators

This paper reviews the equations ax = c and xb = d from a new perspective by studying them in the setting of associative rings with or without involution. Results for rectangular matrices and operators between different Banach and Hilbert spaces are obtained by embedding the ‘rectangles’ into rings of square matrices or rings of operators acting on the same space. Necessary and sufficient conditions using generalized inverses are given for the existence of the hermitian, skew-hermitian, reflexive, antireflexive, positive and real-positive solutions, and the general solutions are described in terms of the original elements or operators. New results are obtained, and many results existing in the literature are recovered and corrected.     

Matrix multiplication is determined by orthogonality and trace

Any associative bilinear multiplication on the set of n-by-n matrices over some field of characteristic not two, that makes the same vectors orthogonal and has the same trace as ordinary matrix multiplication, must be ordinary matrix multiplication or its opposite.     

Matrix algebras with Multiplicative Decomposition Property

We consider the Multiplicative Decomposition Property (the multiplicative analogue of the Riesz Decomposition Property) for entry-wise ordered matrix algebras over the reals. We characterize for which matrix pairs such a decomposition exists and use this result to present necessary and sufficient conditions for a matrix algebra to enjoy the decomposition property by all its positive matrix pairs. Thus we describe all matrix algebras with the decomposition property.     

A matrix problem over a central quadratic skew field extension

Let F⊂G=F(u) be a central quadratic skew field extension (such that the generator u is central in G) and a natural (G,G)-bimodule. We deal with the matrix problem on finding a canonical form for rectangular matrices over W with help of left elementary transformations of their rows and right elementary transformations of columns over G. We solve this problem reducing it in the separable (resp. inseparable) case to the semilinear (resp. pseudolinear) pencil problem.     

Positivity Preserving Hadamard Matrix Functions

For every positive real number p that lies between even integers 2(m − 2) and 2(m − 1) we demonstrate a matrix A = [a_ij] of order 2m such that A is positive definite but the matrix with entries |a_ij|^p is not.     

Frobenius structural matrix algebras

We discuss when the incidence coalgebra of a locally finite preordered set is right co-Frobenius. As a consequence, we obtain that a structural matrix algebra over a field k is Frobenius if and only if it consists, up to a permutation of rows and columns, of diagonal blocks which are full matrix algebras over k.