Locally Adapted Hierarchical Basis Preconditioning

Richard Szeliski

Abstract

This paper develops locally adapted hierarchical basis functions for effectively preconditioning large optimization problems that arise in computer graphics applications such as tone mapping, gradientdomain blending, colorization, and scattered data interpolation. By looking at the local structure of the coefficient matrix and performing a recursive set of variable eliminations, combined with a simplification of the resulting coarse level problems, we obtain bases better suited for problems with inhomogeneous (spatially varying) data, smoothness, and boundary constraints. Our approach removes the need to heuristically adjust the optimal number of preconditioning levels, significantly outperforms previously proposed approaches, and also maps cleanly onto data-parallel architectures such as modern GPUs.

Details

Publication typeArticle
Published inACM Transactions on Graphics
Pages1135-1143
Volume25
Number3
PublisherAssociation for Computing Machinery, Inc.
> Publications > Locally Adapted Hierarchical Basis Preconditioning