Newton's method for the common eigenvector problem

In El Ghazi et al. [Backward error for the common eigenvector problem, CERFACS Report TR/PA/06/16, Toulouse, France, 2006], we have proved the sensitivity of computing the common eigenvector of two matrices A and B, and we have designed a new approach to solve this problem based on the notion of the backward error.If one of the two matrices (saying A) has n eigenvectors then to find the common eigenvector we have just to write the matrix B in the basis formed by the eigenvectors of A. But if there is eigenvectors with multiplicity >1, the common vector belong to vector space of dimension >1 and such strategy would not help compute it.In this paper we use Newton's method to compute a common eigenvector for two matrices, taking the backward error as a stopping criteria.We mention that no assumptions are made on the matrices A and B.     

Constructing weighing matrices by the method of weaving

We describe a way of obtaining new weighing matrices from old, which we call weaving because it involves distributing rows and columns of given matrices along the columns and rows of an array to form a partitioned matrix whose blocks have rank one. The method generalizes both the direct sum and direct product of matrices. We use the method to construct some new weighing matrices of relatively small order. © 1995 John Wiley & Sons, Inc.     

Matrix-free interior point method

In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods and imposes restrictions on the way the preconditioner is computed. A two-step approach is used to design a preconditioner. First, the Newton equation system is regularized to guarantee better numerical properties and then it is preconditioned. The preconditioner is implicit, that is, its computation requires only matrix-vector multiplications with the original problem data. The method is therefore well-suited to problems in which matrices are not explicitly available and/or are too large to be stored in computer memory. Numerical properties of the approach are studied including the analysis of the conditioning of the regularized system and that of the preconditioned regularized system. The method has been implemented and preliminary computational results for small problems limited to 1 million of variables and 10 million of nonzero elements demonstrate the feasibility of the approach.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

An optimum iterative method for solving any linear system with a square matrix

A method is presented to solveAx=b by computing optimum iteration parameters for Richardson's method. It requires some information on the location of the eigenvalues ofA. The algorithm yields parameters well-suited for matrices for which Chebyshev parameters are not appropriate. It therefore supplements the Manteuffel algorithm, developed for the Chebyshev case. Numerical examples are described.     

Generating random correlation matrices based on vines and extended onion method

We extend and improve two existing methods of generating random correlation matrices, the onion method of Ghosh and Henderson [S. Ghosh, S.G. Henderson, Behavior of the norta method for correlated random vector generation as the dimension increases, ACM Transactions on Modeling and Computer Simulation (TOMACS) 13 (3) (2003) 276–294] and the recently proposed method of Joe [H. Joe, Generating random correlation matrices based on partial correlations, Journal of Multivariate Analysis 97 (2006) 2177–2189] based on partial correlations. The latter is based on the so-called D-vine. We extend the methodology to any regular vine and study the relationship between the multiple correlation and partial correlations on a regular vine. We explain the onion method in terms of elliptical distributions and extend it to allow generating random correlation matrices from the same joint distribution as the vine method. The methods are compared in terms of time necessary to generate 5000 random correlation matrices of given dimensions.     

A second-order bundle method to minimize the maximum eigenvalue function

In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace of n×n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the framework of the ?-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence. A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming. Received: February 9, 1998 / Accepted: May 2, 2000?Published online September 20, 2000     

The modified bordering method to evaluate eigenvalues and eigenvectors of normal matrices

A bordering procedure is here proposed to evaluate the eigensystem of hermitian matrices, and more in general of normal matrices, when the spectral decomposition is known of then–1×n–1 principal minor. The procedure is also applicable to special real and nonsymmetric matrices here named quasi-symmetric. The computational cost to write the characteristic polynomial isO(n ²), using a new set of recursive formulas. A modified Brent algorithm is used to find the roots of the polynomial. The eigenvectors are evaluated in a direct way with a computational cost ofO(n ²) for each one. Some numerical considerations indicate where numerical difficulties may occur. Numerical results are given comparing this method with the Givens-Householder one.     

A divide and conquer method for the symmetric tridiagonal eigenproblem

Summary A method is given for calculating the eigenvalues of a symmetric tridiagonal matrix. The method is shown to be stable and for a large class of matrices it is, asymptotically, faster by an order of magnitude than theQR method.     

Numerical solution of fractional differential equations with a Tau method based on Legendre and Bernstein polynomials

In this paper, we state and prove a new formula expressing explicitly the integratives of Bernstein polynomials (or B‐polynomials) of any degree and for any fractional‐order in terms of B‐polynomials themselves. We derive the transformation matrices that map the Bernstein and Legendre forms of a degree‐n polynomial on [0,1] into each other. By using their transformation matrices, we derive the operational matrices of integration and product of the Bernstein polynomials. These matrices together with the Tau method are then utilized to reduce the solution of this problem to the solution of a system of algebraic equations. The method is applied to solve linear and nonlinear fractional differential equations. Copyright © 2013 John Wiley & Sons, Ltd.     

Generalized diagonal dominance in connection with the accelerated overrelaxation (AOR) method

With the definition of generalized diagonal dominant matrices we improve the known results about the intervals of convergence of the (AOR) method for linear systems. We consider this problem for different kinds of matrices and we get some important results forH-matrices.Supported by Instituto Nacional de Investigação Cientifica.     

Gegenbauer wavelet collocation method for the extended Fisher-Kolmogorov equation in two dimensions

Gegenbauer wavelets operational matrices play an important role in the numeric solution of differential equations. In this study, operational matrices of rth integration of Gegenbauer wavelets are derived and used to obtain an approximate solution of the nonlinear extended Fisher-Kolmogorov (EFK) equation in two-space dimension. Nonlinear EFK equation is converted into the linear partial differential equation by quasilinearization technique. Numerical examples have shown that present method is convergent even in the case of a small number of grid points. The results of the presented method are in a good agreement with the results in literature.     

The least-squares method for matrices dependent on parameters

Some algorithms are suggested for constructing pseudoinverse matrices and for solving systems with rectangular matrices whose entries depend on a parameter in polynomial and rational ways. The cases of one- and two-parameter matrices are considered. The construction of pseudoinverse matrices are realized on the basis of rank factorization algorithms. In the case of matrices with polynomial occurrence of parameters, these algorithms are the ΔW-1 and ΔW-2 algorithms for one- and two-parameter matrices, respectively. In the case of matrices with rational occurrence of parameters, these algorithms are the irreducible factorization algorithms. This paper is a continuation of the author's studies of the solution of systems with one-parameter matrices and an extension of the results to the case of two-parameter matrices with polynomial and rational entries. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 176–185. This work was supported by the Russian Foundation of Fundamental Research (grant 94-01-00919). Translated by V. N. Kublanovskaya.     

Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

On the fast Lanczos method for computation of eigenvalues of Hankel matrices using multiprecision arithmetics

The use of the fast Fourier transform (FFT) accelerates Lanczos tridiagonalisation method for Hankel and Toeplitz matrices by reducing the complexity of matrix–vector multiplication. In multiprecision arithmetics, the FFT has overheads that make it less competitive compared with alternative methods when the accuracy is over 10000 decimal places. We studied two alternative Hankel matrix–vector multiplication methods based on multiprecision number decomposition and recursive Karatsuba‐like multiplication, respectively. The first method was uncompetitive because of huge precision losses, while the second turned out to be five to 14 times faster than FFT in the ranges of matrix sizes up to n = 8192 and working precision of b = 32768 bits we were interested in. We successfully applied our approach to eigenvalues calculations to studies of spectra of matrices that arise in research on Riemann zeta function. The recursive matrix–vector multiplication significantly outperformed both the FFT and the traditional multiplication in these studies. Copyright © 2016 John Wiley & Sons, Ltd.     

Convergence of Rump's method for inverting arbitrarily ill-conditioned matrices

In this paper, the problem of inverting regular matrices with arbitrarily large condition number is treated in double precision defined by IEEE 754 floating point standard. In about 1984, Rump derived a method for inverting arbitrarily ill-conditioned matrices. The method requires the possibility to calculate a dot product in higher precision. Rump's method is of theoretical interest. Rump made it clear that inverting an arbitrarily ill-conditioned matrix in single or double precision does not produce meaningless numbers, but contains a lot of information in it. Rump's method uses such inverses as preconditioners. Numerical experiments exhibit that Rump's method converges rapidly for various matrices with large condition numbers. Why Rump's method is so efficient for inverting arbitrarily ill-conditioned matrices is a little mysterious. Thus, to prove its convergence is an interesting problem in numerical error analysis. In this article, a convergence theorem is presented for a variant of Rump's method.     

An elementary method for the calculation of the set of character degrees of somep-groups

Letq be a power of a prime numberp. In this work, we present an elementary method to find out the set of irreducible character degrees of the Sylowp-subgroups ofSp(2n,q) whenq is odd. This simplifies the proof of Previtali [4], where this result was first obtained. This method also works for the groups of unitriangular matrices over finite fields. Research supported by the Basque Government and the University of the Basque Country UPV 127.310-EB160/98.     

A fractional-analytic method of finding Moore-Penrose and drasin pseudo-inverse matrices

We consider a method of finding the Moore-Penrose and Drasin pseudo-inverse matrices by applying the machinery of continued C- and j-fractions. The fractional-analytic method is based on effective passage to the limit as the regularizing parameter tends to zero. Translated fromMatematichni Metodi ta Fiziko-Mekhanichni Polya, Vol. 39, No. 2, 1996, pp. 140–143.     

An interior point method for quadratic programs based on conjugate projected gradients

We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrixQ. The interior point method we describe is a doubly iterative algorithm that invokes aconjugate projected gradient procedure to obtain the search direction. The effect is thatQ appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method istheoretically convergent with onlyone matrix factorization throughout the procedure.     

A restarted Krylov method with inexact inversions

In this paper, we present a new type of restarted Krylov method for calculating the smallest eigenvalues of a symmetric positive definite matrix G. The new framework avoids the Lanczos tridiagonalization process and the use of polynomial filtering. This simplifies the restarting mechanism and allows the introduction of several modifications. Convergence is assured by a monotonicity property that pushes the eigenvalues toward their limits. Another innovation is the use of inexact inversions of G to generate the Krylov matrices. In this approach, the inverse of G is approximated by using an iterative method to solve the related linear system. Numerical experiments illustrate the usefulness of the proposed approach.