THE LANCZOS METHOD www.com SOFTWARE • ENVIRONMENTS • TOOLS The series includes handbooks and software guides as well as monographs on practical implementation of computational methods, environments, and tools. The focus is on making recent developments available in a practical format to researchers and other users of these methods and tools. Editor-in-Chief Jack J. Dongarra University of Tennessee and Oak Ridge National Laboratory Editorial Board James W.
Demmel, University of California, Berkeley Dennis Gannon, Indiana University Eric Grosse, AT&T Bell Laboratories Ken Kennedy, Rice University Jorge J. More, Argonne National Laboratory Software, Environments, and Tools Louis Komzsik, The Lanczos Method: Evolution and Application Bard Ermentrout, Simulating, Analyzing, and Animating Dynamical Systems: A Guide to XPPAUT for Researchers and Students V. Yalamov, LAPACK95 Users' Guide Stefan Goedecker and Adolfy Hoisie, Performance Optimization of Numerically Intensive Codes Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide Lloyd N. Trefethen, Spectral Methods in MATLAB E.
Sorensen, LAPACK Users' Guide, Third Edition Michael W. Berry and Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval lack J. Sorensen, and Henk A. van der Vorst, Numerical Linear Algebra for High-Performance Computers R.
Yang, /ARRACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods Randolph E. Bank, PLTMG: A Software Package for Solving Elliptic Partial Differential Equations, Users' Guide 8. Whaley, ScaLAPACK Users' Guide Greg Astfalk, editor, Applications on Advanced Architecture Computers Francoise Chaitin-Chatelin and Valerie Fraysse, Lectures on Finite Precision Computations Roger W. Hockney, The Science of Computer Benchmarking Richard Barrett, Michael Berry, Tony F.
Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, and Henk van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods E. Sorensen, LAPACK Users' Guide, Second Edition Jack J. Sorensen, and Henk van der Vorst, Solving Linear Systems on Vector and Shared Memory Computers J. Stewart, Unpack Users' Guide www.com Louis Komzsik Schaeffer Automated Simulation, LLC Altadena, California THE LANCZOS METHOD Evolution and Application Siam Society for Industrial and Applied Mathematics Philadelphia www.com Copyright © 2003 by the Society for Industrial and Applied Mathematics 10987654321 All rights reserved.
Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688. Library of Congress Cataloging-in-Publication Data Komzsik, Louis.
The Lanczos method : evolution and application / Louis Komzsik. Includes bibliographical references and index. Computer science-Mathematics.01'51-dc21 2002044643 MATLAB is a registered trademark of The MathWorks, Inc. NASTRAN is a registered trademark of the National Aeronautics and Space Administration.
siam is a registered trademark.com To Stella and Victor www.com This page intentionally left blank www.com Contents Preface xi I EVOLUTION 1 1 The classical Lanczos method 3 1.1 The eigenvalue problem 3 1.2 The method of minimized iterations 4 1.3 Calculation of eigenvalues and eigenvectors 6 1.4 Geometric interpretation 8 2 The Lanczos method in exact arithmetic 9 2.2 Solving the tridiagonal problem 11 2.3 Exact arithmetic algorithm 12 2.4 Computational example 13 3 The Lanczos method in finite precision 17 3.1 Breakdown of the Lanczos process 17 3.2 Measuring and maintaining orthogonality 18 3.3 Monitoring convergence and estimating accuracy 19 3.4 Finite precision algorithm 20 4 Block real symmetric Lanczos method 23 4.1 The block Lanczos method 23 4.2 Measuring and maintaining block orthogonality 25 4.3 Reduction of block tridiagonal form 26 4.4 Block real symmetric algorithm 26 5 Block unsymmetric Lanczos method 29 5.1 Block biorthogonal Lanczos method 29 5.2 Solution of the block tridiagonal problem 30 5.4 Block unsymmetric algorithm 31 5.5 Adapting the block size 32 vii www.com viii Contents 5.7 Maintaining biorthonormality 34 II APPLICATIONS 37 6 Industrial implementation of the Lanczos method 39 6.2 Frequency domain decomposition 41 6.3 Geometric domain decomposition 42 6.2 Partitioned matrix decomposition 43 6.4 Partitioned Lanczos step 45 6.4 Parallel computational strategy 45 7 Free undamped vibrations 47 7.1 Analysis of mechanical systems 47 7.2 Generalized linear eigenvalue problem 49 7.3 Normal modes analysis application 50 8 Free damped vibrations 53 8.1 Generalized quadratic eigenvalue problem 53 8.2 Recovery of physical solution 54 8.4 Implicit operator multiplication 57 8.5 Implicit operator algorithm 59 8.6 Complex eigenvalue analysis application 60 9 Forced vibration analysis 63 9.1 The interior acoustic problem 63 9.2 Fluid-structure interaction 65 9.3 Coupled forced vibration problem 66 9.4 Pade approximation via the Lanczos method 67 9.1 Transfer function calculation 67 9.2 Approximate transfer function 68 9.5 Acoustic optimization application 69 10 Linear systems and the Lanczos method 71 10.3 Recursive approximate solution 73 10.4 Lanczos linear solver algorithm 74 10.5 Linear static analysis application 75 www.com Contents ix Closing Remarks 77 A Brief Biography of Cornelius Lanczos 79 Bibliography 81 Index 85 www.com This page intentionally left blank www.com Preface The subject of this book, the method of Lanczos, is probably one of the most influ- ential methods of computational mathematics in the second half of the 20th century. Since Lanczos's seminal paper [2] in 1950, despite some early setbacks about the applicability of the method in computers with finite precision arithmetic, the method found its way into many aspects of science and engineering. The applications are so widespread that it is practically impossible to describe them in a single book. This book follows the evolution of the method as it became more and more established and understood, and began to solve a wide variety of engineering analysis problems.
My personal involvement with and admiration of the method started in the early 1970s in Budapest as a graduate student at the successor of Lanczos's alma mater. While at that time both Lanczos and his method had somewhat tarnished reputations, for political and numerical reasons, respectively, I was taken by the beauty of the three-member recurrence. The second half of the 1970s saw the restoration of the numerical reputation of the method worldwide, and by the end of the decade Lanczos was also put on his well-deserved pedestal, even in Hungary. The material in this book comes from seminars and lectures I had given on the topic during the past two decades.
The seminars, held by leading corporations of the automobile and aerospace industries in the United States, Europe, and Asia, were attended by engineers and computer scientists and focused on applications of the method in commercial finite element analysis, specifically in structural analysis. The lectures I had given recently as a SIAM Visiting Lecturer at various academic institutions were attended by both faculty and students and centered on practical implementation and computational performance issues. The interest of the audience in both camps and the lack of a text encompassing the evolution of the method contributed to the decision to write this book. I hope that the readers share this interest, enjoy a brief travel of time through the history of the method, and find the book useful in their applications.
The book has two distinct parts. The first part, Chapters 1 through 5, demonstrates the evolution of the method from the review of Lanczos's original method to the state-of- the-art adaptive methods. The second part, Chapters 6 through 10, addresses the practical implementation and industrial application of the method. Specifically, in Chapters 7, 8, and 9 the well-established industrial applications of normal modes and complex eigenvalue analyses, as well as the frequency response analysis, are discussed.
The book concludes with the application of the Lanczos method for the solution of linear systems. While heavy on mathematical content, in order to achieve readability, rigorous state- ment of theorems and proofs are omitted. Similarly, topics in the linear algebraic foundation xi www.com xii Preface (QR and singular value decomposition, Givens rotations, etc.) are not discussed in detail to keep the focus sharp. Several chapters contain a computational algorithm enabling the reader to implement some of the methods either in a MATLAB environment or in a high-level programming language.
During the past quarter century I have cooperated with many people in various as- pects of the Lanczos method. I specifically thank Prof. Beresford Parlett of UC Berkeley and Prof. Gene Golub of Stanford University for their most valuable theoretical influence, which I enjoyed from their books as well as personal contacts.
I am also very much in- debted to Dr. Horst Simon of Berkeley National Laboratory, Dr. John Lewis of Boeing, and Prof. Zhaojun Bai of UC Davis for their very important cooperation in the practical imple- mentation aspects of the Lanczos method.
Finally, special thanks are due to my colleague, Dr. Tom Kowalski, who, besides participating in the implementation of some of the methods mentioned in this book into NASTRAN, has also dutifully proofread the manuscript and provided valuable corrections and suggestions. Louis Komzsik 2002 www.com Part I EVOLUTION 1 www.com This page intentionally left blank www.com Chapter 1 The classical Lanczos method At the time of Lanczos's work on the eigenvalue problem during the Second World War, most methods focused on finding the characteristic polynomial of matrices in order to find their eigenvalues. In fact, Lanczos's original paper [2] was also mostly concerned with this problem; however, he was trying to reduce the round-off errors in such calculations.
He called his method the method of minimized iterations, which we will now review to lay the foundation.1 The eigenvalue problem For a real, square matrix A of order n, the product defines a quadratic form. This is a continuous function of x = (x 1 , x2,. When A is symmetric positive definite, the equation defines an n-dimensional ellipsoid in Rn which is in all likelihood rotated. The eigen- value problem is to find the n principal axes of this ellipsoid which are the eigenvectors The square roots of the lengths of the principal axes are the eigenval- ues.
They satisfy the equation This is easy to verify considering the fact that the directions of the principal axes of the ellipsoid are where the surface normal n is colinear with the principal axis location vector pointing to the surface , where c is a scalar constant. Since the normal points into the direction of the gradient, 3 www. The classical Lanczos method it follows that c is I/ .2 The method of minimized iterations Lanczos first considered symmetric matrices (AT = A) and set out to find the characteristic polynomial of in order to solve where u is an eigenvector and m, is the corresponding eigenvalue. In deference to Lanczos, in this section we adhere to his original notation as much as possible.
Specifically, the inner products commonly written as b bo in today's literature is noted below as b. Lanczos sought the characteristic polynomial by generating a sequence of trial vectors, resulting in a successive set of polynomials. Starting from a randomly selected vector bo, the new vector b1 is chosen as a certain linear combination of bo and Abo, Here the parameter ao is found from the condition of b\ having as small magnitude as possible: Differentiation and algebra yields It is important to notice that the new b\ vector is orthogonal to the original bo vector, i., Continuing the process, one can find a bi vector by choosing the linear combination where once again the constants are defined by the fact that b shall be minimal. Some algebraic work yields Since the new vector is orthogonal to both b\ and b0.
Once more continuing the process, we need www. The method of minimized iterations 5 However, in view of the orthogonality of bi to both previous vectors, we get The brilliant observation of Lanczos is that in every step of the iteration we will need only two correction terms: the famous three-member recurrence. The process established by Lanczos is now The equality to zero on the rath recurrence equation means the end of the process.