A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints

DOI10.1137/090771995MaRDI QIDQ3083582zbMATH OpenOpenAlexFDO

Authors Dorit Ron, Ilya Safro, Achi Brandt

Publication date 22 March 2011

Published in Multiscale Modeling & Simulation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.3208

zbMATH Keywords

constrained optimizationdensity constraintsfull approximation schemegeometric multigridgraph drawing and visualizationgraphical exampleslayout problems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Abstract: The two-dimensional layout optimization problem reinforced by the efficient space utilization demand has a wide spectrum of practical applications. Formulating the problem as a nonlinear minimization problem under planar equality and/or inequality density constraints, we present a linear time multigrid algorithm for solving correction to this problem. The method is demonstrated on various graph drawing (visualization) instances.

Recommendations

• On an energy minimizing basis for algebraic multigrid methods
• Algorithmic aspects of multigrid methods for optimization in shape spaces
• A linearly constrained optimization problem for planar grid generation
• A general interpolation strategy for algebraic multigrid using energy minimization
• A multigrid approach to discretized optimization problems
• A practical guide to direct optimization for planar grid-generation
• An Energy-minimizing Interpolation for Robust Multigrid Methods
• A nearly optimal multigrid method for general unstructured grids
• Parallel Energy-Minimization Prolongation for Algebraic Multigrid
• Preconditioned conjugate gradient method for finding minimal energy surfaces on Powell-Sabin triangulations

Cited in

(1)

• An optimal layout of multigrid networks

This page was built for publication: A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083582)