An application of preconditioned conjugate gradients to relative placement in chip design
Christian Kredler, Christian Zillober, Frank M. Johannes, Georg Sigl · International Journal for Numerical Methods in Engineering · 1993
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.