Killian Miller
Top-level Acceleration of an AMG Method for Markov Chains Via the Ellipsoid Method

University of Waterloo
Department of Applied Mathematics
200 University Avenue West
Waterloo
Ontario N2L 3G1
killian.miller@gmail.com
Hans De Sterck
Geoffrey Sanders

In many application areas including information retrieval, networking systems and performance modeling of communication systems, the steady-state distribution vector of an irreducible Markov chain is of interest, and it is often difficult to compute. The steady-state vector is the solution to a nonsymmetric eigenproblem with known eigenvalue, $B{\bf x}= {\bf x}$, subject to the probability constraints $\Vert{\bf x}\Vert _1 = 1$ and $x_i \geq 0~\forall i$, where $B$ is a column-stochastic matrix. A relatively new approach to solving these eigenvalue problems has been the application of multigrid techniques. Recently, scalable multilevel methods based on smoothed aggregation [2] and algebraic multigrid [1] were proposed to solve such problems. The performance of these methods was investigated for a wide range of numerical test problems, and for most test cases, near-optimal multigrid efficiency was obtained.

In [3], it was shown how the convergence of these multilevel methods can be accelerated by the addition of an outer iteration, with the resulting accelerated algorithm similar in principle to a preconditioned flexible Krylov subspace method. The acceleration was performed by selecting a linear combination of previous fine-level iterates to minimize a functional $\mathcal{F}$ over the space of probability vectors $\mathcal{P}$. Only the $m$ most recent fine-level iterates were used, where $m$ is the window size. The functional was taken as the 2-norm of the residual, $\mathcal{F}_2({\bf x}) = \Vert(I-B){\bf x}\Vert _2$; consequently each acceleration step consisted of solving a small $(m \leq 5)$ quadratic programming problem, for which both constrained and unconstrained variants were considered.

In this talk we consider a different functional, namely, $\mathcal{F}_1({\bf x}) = \Vert(I-B){\bf x}\Vert _1$. This gives rise to the following nonlinear convex programming problem (CPP) which must be solved at each acceleration step:

$$\quad \mathcal{F}_1({\bf x})$$ minimize

$$\quad {\bf x}\in (\mathcal{P}\cap \mathcal{V}),$$ subject to

where $\mathcal{V}$ is the space spanned by the $m$ most recent fine-level iterates. To solve this CPP we use a variation of the well-known ellipsoid algorithm from linear optimization. Our motivation for considering the functional $\mathcal{F}_1$ is from a numerical standpoint: the 1-norm optimization problem may be easier and faster to solve than the 2-norm problem. Moreover, since $\mathcal{F}_1({\bf x}) \ll 1$ implies that $\mathcal{F}_2({\bf x}) \ll 1$, the acceleration in the 1-norm case should be comparable to the acceleration in the 2-norm case. We quantify our approach by directly comparing our results with those obtained in [3], for a variety of test problems. For simplicity we focus solely on constrained acceleration of the algebraic multigrid method for Markov chains from [1].

References

[1]

HANS DE STERCK, THOMAS A. MANTEUFFEL, STEPHEN F. MCCORMICK, KILLIAN MILLER, JOHN RUGE, AND GEOFFREY SANDERS, Algebraic multigrid for Markov chains, SIAM J. Sci. Comp., accepted, 2009.

[2]

HANS DE STERCK, THOMAS A. MANTEUFFEL, STEPHEN F. MCCORMICK, KILLIAN MILLER, JAMES PEARSON, JOHN RUGE, AND GEOFFREY SANDERS, Smoothed aggregation multigrid for Markov chains, SIAM J. Sci. Comp., accepted, 2009.

[3]

HANS DE STERCK, THOMAS A. MANTEUFFEL, KILLIAN MILLER, AND GEOFFREY SANDERS, Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains, submitted to Advances in Computational Mathematics, Sept. 2009.