Iterant recombination with one-norm minimization for multilevel Markov chain algorithms via the ellipsoid method

Hans De Sterck, Killian Miller, Geoffrey Sanders

Research output: Contribution to journalArticleResearchpeer-review


Recently, it was shown how the convergence of a class of multigrid methods for computing the stationary distribution of sparse, irreducible Markov chains can be accelerated by the addition of an outer iteration based on iterant recombination. The acceleration was performed by selecting a linear combination of previous fine-level iterates with probability constraints to minimize the two-norm of the residual using a quadratic programming method. In this paper we investigate the alternative of minimizing the one-norm of the residual. This gives rise to a nonlinear convex program which must be solved at each acceleration step. To solve this minimization problem we propose to use a deep-cuts ellipsoid method for nonlinear convex programs. The main purpose of this paper is to investigate whether an iterant recombination approach can be obtained in this way that is competitive in terms of execution time and robustness. We derive formulas for subgradients of the one-norm objective function and the constraint functions, and show how an initial ellipsoid can be constructed that is guaranteed to contain the exact solution and give conditions for its existence. We also investigate using the ellipsoid method to minimize the two-norm. Numerical tests show that the one-norm and twonorm acceleration procedures yield a similar reduction in the number of multigrid cycles. The tests also indicate that onenorm ellipsoid acceleration is competitive with two-norm quadratic programming acceleration in terms of running time with improved robustness.

Original languageEnglish
Pages (from-to)51-65
Number of pages15
JournalComputing and Visualization in Science
Issue number2
Publication statusPublished - Feb 2011
Externally publishedYes


  • Convex programming
  • Ellipsoid algorithm
  • Iterant recombination
  • Markov chain
  • Multigrid

Cite this