An application of preconditioned conjugate gradients to relative placement in chip design

Christian Kredler, Christian Zillober, Frank Johannes, Georg Sigl

Research output: Contribution to journalArticlepeer-review

Abstract

In distance geometry problems and many other applications, we are faced with the optimization of high‐dimensional quadratic functions subject to linear equality constraints. A new approach is presented that projects the constraints, preserving sparsity properties of the original quadratic form such that well‐known preconditioning techniques for the conjugate gradient method remain applicable. Very‐large‐scale cell placement problems in chip design have been solved successfully with diagonal and incomplete Cholesky preconditioning. Numerical results produced by a FORTRAN 77 program illustrate the good behaviour of the algorithm.

Original languageEnglish
Pages (from-to)255-271
Number of pages17
JournalInternational Journal for Numerical Methods in Engineering
Volume36
Issue number2
DOIs
StatePublished - 30 Jan 1993

Fingerprint

Dive into the research topics of 'An application of preconditioned conjugate gradients to relative placement in chip design'. Together they form a unique fingerprint.

Cite this