An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

On computing PageRank via lumping the Google matrix

Computing Google’s PageRank via lumping the Google matrix was recently analyzed in [I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl. 29 (2007) 1281–1296]. It was shown that all of the dangling nodes can be lumped into a single node and the PageRank could be obtained by applying the power method to the reduced matrix. Furthermore, the stochastic reduced matrix had the same nonzero eigenvalues as the full Google matrix and the power method applied to the reduced matrix had the same convergence rate as that of the power method applied to the full matrix. Therefore, a large amount of operations could be saved for computing the full PageRank vector.     

Eigenvalues of rank-one updated matrices with some applications

We prove a spectral perturbation theorem for rank-one updated matrices of special structure. Two applications of the result are given to illustrate the usefulness of the theorem. One is for the spectrum of the Google matrix and the other is for the algebraic simplicity of the maximal eigenvalue of a positive matrix.     

The distance from a matrix polynomial to matrix polynomials with a prescribed multiple eigenvalue

For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).     

The Jordan canonical form for a class of zero-one matrices

Let f:N→N be a function. Let A_n=(a_ij) be the n×n matrix defined by a_ij=1 if i=f(j) for some i and j and a_ij=0 otherwise. We describe the Jordan canonical form of the matrix A_n in terms of the directed graph for which A_n is the adjacency matrix. We discuss several examples including a connection with the Collatz 3n+1 conjecture.     

Singular-value-like decomposition for complex matrix triples

The classical singular value decomposition for a matrix A∈C^m×n is a canonical form for A that also displays the eigenvalues of the Hermitian matrices AA^∗ and A^∗A. In this paper, we develop a corresponding decomposition for A that provides the Jordan canonical forms for the complex symmetric matrices and . More generally, we consider the matrix triple , where are invertible and either complex symmetric or complex skew-symmetric, and we provide a canonical form under transformations of the form , where X,Y are nonsingular.     

A preconditioning approach to the pagerank computation problem

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ER_U method, and we observe that ER_U can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ER_U superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.     

Jordan structures of alternating matrix polynomials

Alternating matrix polynomials, that is, polynomials whose coefficients alternate between symmetric and skew-symmetric matrices, generalize the notions of even and odd scalar polynomials. We investigate the Smith forms of alternating matrix polynomials, showing that each invariant factor is an even or odd scalar polynomial. Necessary and sufficient conditions are derived for a given Smith form to be that of an alternating matrix polynomial. These conditions allow a characterization of the possible Jordan structures of alternating matrix polynomials, and also lead to necessary and sufficient conditions for the existence of structure-preserving strong linearizations. Most of the results are applicable to singular as well as regular matrix polynomials.     

Smooth factorizations of matrix valued functions and their derivatives

Summary In this paper we study the numerical factorization of matrix valued functions in order to apply them in the numerical solution of differential algebraic equations with time varying coefficients. The main difficulty is to obtain smoothness of the factors and a numerically accessible form of their derivatives. We show how this can be achieved without numerical differentiation if the derivative of the given matrix valued function is known. These results are then applied in the numerical solution of differential algebraic Riccati equations. For this a numerical algorithm is given and its properties are demonstrated by a numerical example.     

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.     

Analysis of a Stokes interface problem

We consider a stationary Stokes problem with a piecewise constant viscosity coefficient. For the variational formulation of this problem we prove a well-posedness result in which the constants are uniform with respect to the jump in the viscosity coefficient. We apply a standard discretization with a pair of LBB stable finite element spaces. The main result of the paper is an infsup result for the discrete problem that is uniform with respect to the jump in the viscosity coefficient. From this we derive a robust estimate for the discretization error. We prove that the mass matrix with respect to some suitable scalar product yields a robust preconditioner for the Schur complement. Results of numerical experiments are presented that illustrate this robustness property. This author was supported by the German Research Foundation through the guest program of SFB 540     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

Asymptotics in Bayesian decision theory with applications to global robustness

We provide the rate of convergence of the Bayes action derived from non smooth loss functions involved in Bayesian robustness. Such loss functions are typically not twice differentiable but admit right and left second derivatives. The asymptotic limit of three measures of global robustness is given. These measures are the range of the Bayes actions set associated with a class of loss functions, the maximum regret of using a particular loss when the subjective loss belongs to a given class and the range of the posterior expected loss when the loss ranges over a given class. An application to prior robustness with density ratio classes is provided.     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Mixing times with applications to perturbed Markov chains

A measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic , where {π_j} is the stationary distribution and m_ij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that η_i = η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities.     

Convergence of a generalized MSSOR method for augmented systems

Recently, Wu et al. [S.-L. Wu, T.-Z. Huang, X.-L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math. 228 (1) (2009) 424-433] introduced a modified SSOR (MSSOR) method for augmented systems. In this paper, we establish a generalized MSSOR (GMSSOR) method for solving the large sparse augmented systems of linear equations, which is the extension of the MSSOR method. Furthermore, the convergence of the GMSSOR method for augmented systems is analyzed and numerical experiments are carried out, which show that the GMSSOR method with appropriate parameters has a faster convergence rate than the MSSOR method with optimal parameters.     

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.     

Generalized Eulerian numbers and the topology of the Hessenberg variety of a matrix

Let Agl(n, C) and let p be a positive integer. The Hessenberg variety of degree p for A is the subvariety Hess(p, A) of the complete flag manifold consisting of those flags S ₁ S _n–1 in ⁿ which satisfy the condition AS _i S _i+p ,for all i. We show that if A has distinct eigenvalues, then Hess(p, A) is smooth and connected. The odd Betti numbers of Hess(p, A) vanish, while the even Betti numbers are given by a natural generalization of the Eulerian numbers. In the case where the eigenvalues of A have distinct moduli, |₁|<<|₁|, these results are applied to determine the dimension and topology of the submanifold of U(n) consisting of those unitary matrices P for which A ₀=P ^-1 AP is in Hessenberg form and for which the diagonal entries of the QR-iteration initialized at A ₀ converge to a given permutation of ₁,_n.Research partially supported by the National Science Foundation under Grant ECS-8696108.     

Google PageRanking problem: The model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1−c)ev^T have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0<c<1, v is a nonnegative probability vector, and e is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector y(c) such that y(c)^TG(c)=y(c)^T and y(c)^Te=1. This PageRank vector y(c) can be computed effectively by the power method.We consider a square complex matrix A and nonzero complex vectors x and v such that Ax=λx and v^∗x=1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left λ-eigenvector of A(c)=cA+(1−c)λxv^∗ as a function of a complex variable c. If λ is a semisimple eigenvalue of A, there is a uniquely determined projection N such that lim_c→1y(c)=Nv for all v; this limit may fail to exist for some v if λ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix G(c) with a complex parameter c. We study regularity, limits, expansions, and conditioning of y(c) and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with c close or equal to 1. An interpretation of the limit vector Nv and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution of the paper on modeling issues.