Multilevel Optimization in VLSICAD
In the last few decades, multiscale algorithms have become a dominant trend in large-scale scientific computation. Researchers have successfully applied these methods to a wide range of simulation and optimization problems. This book gives a general overv
- PDF / 32,998,312 Bytes
- 311 Pages / 439 x 666 pts Page_size
- 60 Downloads / 287 Views
COMBINATORIAL OPTIMIZATION VOLUME 14
Through monographs and contributed works the objective of the series is to publish state of the art expository research covering all topics in the field of combinatorial optimization. In addition, the series will include books which are suitable for graduate level courses in computer science, engineering, business, applied mathematics, and operations research. Combinatorial (or discrete) optimization problems arise in various applications, including communications network design, VLSI design, machine vision, airline crew scheduling, corporate planning, computer-aided design and manufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. The topics of the books will cover complexity analysis and algorithm design (parallel and serial), computational experiments and applications in science and engineering. Series Editors: Ding-Zhu Du, University of Minnesota Panos M. Pardalos, University of Florida Advisory Editorial Board: Afonso Ferreira, CNRS-LIP ENS Lyon Jun Gu, University of Calgary David S. Johnson, AT&T Research James B. Orlin, M.I.T. Christos H. Papadimitriou, University of California at Berkeley Fred S. Roberts, Rutgers University Paul Spirakis, Computer Tech Institute (CTl)
The titles published in this series are listed at the end of this volume.
Multilevel Optimization in VLSICAD edited by
Jason Cong University of California, Los Angeles, U.S.A.
and
Joseph R. Shinned University of California, Los Angeles, U.S.A .
Springer-Science+Business Media, B.Y.
A c.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-5240-0 ISBN 978-1-4757-3748-6 (eBook) DOl 10.1007/978-1-4757-3748-6
Printed on acidjree paper
All Rights Reserved © 2003 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 2003. Softcover reprint of the hardcover 1st edition 2003 No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work.
Contents
List of Figures
ix
List of Tables
xiii
Preface
xv
Chapter 1 Multigrid Solvers and Multilevel Optimization Strategies Achi Brandt and Dorit Ron 1 Unconstrained quadratic optimization and basic multiscale concepts 2 Linear geometric multigrid 3 Algebraic multigrid (AMG) 4 Numerical homogenization: High-accuracy coarsening 5 Non-symmetric and highly indefinite matrices 6 Non-local equations: Dense matrices 7 Non-quadratic optimization: Nonlinear systems 8 Constrained optimization and eigenproblems 9 Non-deterministic systems 10 Global optimization: Multilevel annealing 11 Graph and hypergraph problems 12 Multilevel formulation
Chapter 2 An Exploration
