Preface xi The writing style is an uneasy mixture of two influences.In private life,the author has written fourteen published science fiction and mystery short stories.When one has described zeppelins jousting in the heavy atmosphere of another world or a stranded ex- plorer alone on an artificial toroidal planet,it is difficult to write with the expected scientific dullness. Nonetheless,I have not been too proud to forget most of the wise precepts I learned in college English:the book makes heavy use of both the passive voice and the editorial "we". When I was still a postdoc,a kindly journal editor took me in hand,and circled every single "I"in red.The scientific abhorrence of the personal pronoun,the active voice,and lively writing is as hypocritical as the Victorian horror of"breast"and "pregnant".Nevertheless, most readers are so used to the anti-literature of science that what would pass for good writing elsewhere would be too distracting.So I have done my best to write a book that is not about its style but about its message. Like any work,this volume reflects the particular interests and biases of the author. While a Harvard undergraduate,I imagined that I would grow up in the image of my pro- fessors:a pillar of the A.M.S.,an editorial board member for a dozen learned journals,and captain and chief executive officer of a large company of graduate students and postdocs. My actual worldline has been amusingly different. I was once elected to a national committee,but only after my interest had shifted.I said nothing and was not a nuisance.I have never had any connection with a journal except as a reviewer.In twelve years at Michigan,I have supervised a single Ph.D.thesis.And more than three-quarters of my 65 papers to date have had but a single author. This freedom from the usual entanglements has allowed me to follow my interests: chemical physics as an undergraduate,dynamic meteorology as a graduate student,hydro- dynamic stability and equatorial fluid mechanics as an assistant professor,nonlinear waves and a stronger interest in numerical algorithms after I was tenured.This book reflects these interests:broad,but with a bias towards fluid mechanics,geophysics and waves. I have also tried,not as successfully as I would have wished,to stress the importance of analyzing the physics of the problem before,during,and after computation.This is partly a reflection of my own scientific style:like a sort of mathematical guerrilla,I have ambushed problems with Pade approximants and perturbative derivations of the Korteweg-de Vries equation as well as with Chebyshev polynomials;numerical papers are only half my pub- lished articles. However,there is a deeper reason:the numerical agenda is always set by the physics. The geometry,the boundary layers and fronts,and the symmetries are the topography of the computation.He or she who would scale Mt.Everest is well-advised to scout the passes before beginning the climb. When I was an undergraduate-ah,follies of youth-I had a quasi-mystical belief in the power of brute force computation. Fortunately,I learned better before I could do too much damage.Joel Primack(to him be thanks)taught me John Wheeler's First Moral Principle:Never do a calculation until you already know the answer. The point of the paradox is that one can usually deduce much about the solution- orders-of-magnitude,symmetries,and so on-before writing a single line of code.A thousand errors have been published because the authors had no idea what the solution ought to look like.For the scientist,as for Sherlock Holmes,it is the small anomalies that are the clues to the great pattern.One cannot appreciate the profound significance of the unexpected without first knowing the expected. The during-and-after theory is important,too.My thesis advisor,Richard Lindzen, never had much interest in computation per se,and yet he taught me better than anyone else the art of good scientific number-crunching.When he was faced with a stiff boundary
Preface xi The writing style is an uneasy mixture of two influences. In private life, the author has written fourteen published science fiction and mystery short stories. When one has described zeppelins jousting in the heavy atmosphere of another world or a stranded explorer alone on an artificial toroidal planet, it is difficult to write with the expected scientific dullness. Nonetheless, I have not been too proud to forget most of the wise precepts I learned in college English: the book makes heavy use of both the passive voice and the editorial “we”. When I was still a postdoc, a kindly journal editor took me in hand, and circled every single “I” in red. The scientific abhorrence of the personal pronoun, the active voice, and lively writing is as hypocritical as the Victorian horror of “breast” and “pregnant”. Nevertheless, most readers are so used to the anti-literature of science that what would pass for good writing elsewhere would be too distracting. So I have done my best to write a book that is not about its style but about its message. Like any work, this volume reflects the particular interests and biases of the author. While a Harvard undergraduate, I imagined that I would grow up in the image of my professors: a pillar of the A. M. S., an editorial board member for a dozen learned journals, and captain and chief executive officer of a large company of graduate students and postdocs. My actual worldline has been amusingly different. I was once elected to a national committee, but only after my interest had shifted. I said nothing and was not a nuisance. I have never had any connection with a journal except as a reviewer. In twelve years at Michigan, I have supervised a single Ph. D. thesis. And more than three-quarters of my 65 papers to date have had but a single author. This freedom from the usual entanglements has allowed me to follow my interests: chemical physics as an undergraduate, dynamic meteorology as a graduate student, hydrodynamic stability and equatorial fluid mechanics as an assistant professor, nonlinear waves and a stronger interest in numerical algorithms after I was tenured. This book reflects these interests: broad, but with a bias towards fluid mechanics, geophysics and waves. I have also tried, not as successfully as I would have wished, to stress the importance of analyzing the physics of the problem before, during, and after computation. This is partly a reflection of my own scientific style: like a sort of mathematical guerrilla, I have ambushed problems with Pade approximants and perturbative derivations of the Korteweg-deVries ´ equation as well as with Chebyshev polynomials; numerical papers are only half my published articles. However, there is a deeper reason: the numerical agenda is always set by the physics. The geometry, the boundary layers and fronts, and the symmetries are the topography of the computation. He or she who would scale Mt. Everest is well-advised to scout the passes before beginning the climb. When I was an undergraduate — ah, follies of youth — I had a quasi-mystical belief in the power of brute force computation. Fortunately, I learned better before I could do too much damage. Joel Primack (to him be thanks) taught me John Wheeler’s First Moral Principle: Never do a calculation until you already know the answer. The point of the paradox is that one can usually deduce much about the solution — orders-of-magnitude, symmetries, and so on — before writing a single line of code. A thousand errors have been published because the authors had no idea what the solution ought to look like. For the scientist, as for Sherlock Holmes, it is the small anomalies that are the clues to the great pattern. One cannot appreciate the profound significance of the unexpected without first knowing the expected. The during-and-after theory is important, too. My thesis advisor, Richard Lindzen, never had much interest in computation per se, and yet he taught me better than anyone else the art of good scientific number-crunching. When he was faced with a stiff boundary
xii Preface value problem,he was not too proud to run up and down the halls,knocking on doors, until he finally learned of a good algorithm:centered differences combined with the tridi- agonal elimination described in Appendix B.This combination had been known for twenty years,but was only rarely mentioned in texts because it was hard to prove convergence the- orems.1 He then badgered the programming staff at the National Center for Atmospheric Research to help him code the algorithm for the most powerful computer then available, the CDC 7600,with explicit data swaps to and from the core. A scientist who is merely good would have stopped there,but Lindzen saw from the numerical output that equatorial waves in vertical shear satisfied the separation-of-scales requirement of singular perturbation theory.He then wrote two purely analytical papers to derive the perturbative approximation,and showed it agreed with his numerical cal- culations.The analysis was very complicated-a member of the National Academy of Sciences once described it to me,laughing.as"the most complicated damn thing I've ever seen"-but the final answers fits on one line. In sad contrast,I see far too many students who sit at their workstation,month after month,trying to batter a problem into submission.They never ask for help,though Michi- gan has one of the finest and broadest collections of arithmurgists on the planet.Nor will they retreat to perturbation theory,asymptotic estimates,or even a little time alone in the corner. It is all too easy to equate multiple windows with hard work,and multiple contour plots with progress.Nevertheless,a scientist by definition is one who listens for the voice of God.It is part of the fallen state of man that He whispers. In order that this book may help to amplify those whispers,I have been uninhibited in expressing my opinions.Some will be wrong:some will be soon outdated.2 Nevertheless, I hope I may be forgiven for choosing to stick my neck out rather than drown the reader in a sea of uninformative blandness.The worst sin of a thesis advisor or a textbook writer is to have no opinions. Preface to the Second Edition,January,1999] In revising this book ten years after,I deleted the old Chapter 11(case studies of fluid computations)and Appendix G(least squares)and added four new chapters on eigen- value problems,aliasing and spectral blocking.the slow manifold and Nonlinear Galerkin theory,and semi-Lagrangian spectral methods.All of the chapters have been updated and most have been rewritten.Chapter 18 has several new sections on polar coordinates.Ap- pendix E contains a new table giving the transformations of first and second derivatives for a two-dimensional map.Appendix F has new analytical formulas for the Legendre- Lobatto grid points up to nine-point grids,which is sufficient for most spectral element applications. My second book,Weakly Nonlocal Solitary Waves and Beyond-All-Orders-Asymptotics(Kluwer, 1998)has two chapters that amplify on themes in this volume.Chapter 8 is an expanded version of Appendices C and D here,describing a much wider range of strategies for non- linear algebraic equations and for initializing interations.Chapter 9 explains how a stan- dard infinite interval basis can be extended to approximate functions that oscillate rather than decay-to-zero at infinity. Other good books on spectral methods have appeared in recent years.These and a selection of review articles are catalogued in Chapter 23. 1Alas,numerical analysis is still more proof-driven than accomplishment-driven even today. 2Surely.too,the book has typographical errors,and the reader is warned to check formulas and tables before using them
xii Preface value problem, he was not too proud to run up and down the halls, knocking on doors, until he finally learned of a good algorithm: centered differences combined with the tridiagonal elimination described in Appendix B. This combination had been known for twenty years, but was only rarely mentioned in texts because it was hard to prove convergence theorems.1 He then badgered the programming staff at the National Center for Atmospheric Research to help him code the algorithm for the most powerful computer then available, the CDC 7600, with explicit data swaps to and from the core. A scientist who is merely good would have stopped there, but Lindzen saw from the numerical output that equatorial waves in vertical shear satisfied the separation-of-scales requirement of singular perturbation theory. He then wrote two purely analytical papers to derive the perturbative approximation, and showed it agreed with his numerical calculations. The analysis was very complicated — a member of the National Academy of Sciences once described it to me, laughing, as “the most complicated damn thing I’ve ever seen” — but the final answers fits on one line. In sad contrast, I see far too many students who sit at their workstation, month after month, trying to batter a problem into submission. They never ask for help, though Michigan has one of the finest and broadest collections of arithmurgists on the planet. Nor will they retreat to perturbation theory, asymptotic estimates, or even a little time alone in the corner. It is all too easy to equate multiple windows with hard work, and multiple contour plots with progress. Nevertheless, a scientist by definition is one who listens for the voice of God. It is part of the fallen state of man that He whispers. In order that this book may help to amplify those whispers, I have been uninhibited in expressing my opinions. Some will be wrong; some will be soon outdated.2 Nevertheless, I hope I may be forgiven for choosing to stick my neck out rather than drown the reader in a sea of uninformative blandness. The worst sin of a thesis advisor or a textbook writer is to have no opinions. [Preface to the Second Edition, January, 1999] In revising this book ten years after, I deleted the old Chapter 11 (case studies of fluid computations) and Appendix G (least squares) and added four new chapters on eigenvalue problems, aliasing and spectral blocking, the slow manifold and Nonlinear Galerkin theory, and semi-Lagrangian spectral methods. All of the chapters have been updated and most have been rewritten. Chapter 18 has several new sections on polar coordinates. Appendix E contains a new table giving the transformations of first and second derivatives for a two-dimensional map. Appendix F has new analytical formulas for the LegendreLobatto grid points up to nine-point grids, which is sufficient for most spectral element applications. My second book, Weakly Nonlocal Solitary Waves and Beyond-All-Orders-Asymptotics(Kluwer, 1998) has two chapters that amplify on themes in this volume. Chapter 8 is an expanded version of Appendices C and D here, describing a much wider range of strategies for nonlinear algebraic equations and for initializing interations. Chapter 9 explains how a standard infinite interval basis can be extended to approximate functions that oscillate rather than decay-to-zero at infinity. Other good books on spectral methods have appeared in recent years. These and a selection of review articles are catalogued in Chapter 23. 1Alas, numerical analysis is still more proof-driven than accomplishment-driven even today. 2Surely, too, the book has typographical errors, and the reader is warned to check formulas and tables before using them
Preface xiii My original plan was to build a bibliographical database on spectral methods and ap- plications of spectral algorithms that could be printed in full here.Alas,this dream was overtaken by events:as the database grew past 2000 items,I was forced to limit the bib- liography to 1025 references.Even so,this partial bibliography and the Science Citation Index should provide the reader with ample entry points into any desired topic.The complete database is available online at the author's homepage,currently at http://www- personal.engin.umich.edu/~jpboyd.To paraphrase Newton,it is better to stand on the shoulders of giants than to try to recreate what others have already done better. Spectral elements have become an increasingly important part of the spectral world in the last decade.However,the first edition,with but a single chapter on spectral elements, was almost 800 pages long.(Students irrevently dubbed it the "Encyclopedia Boydica".) So,I have reluctantly included only the original chapter on domain decomposition in this edition.A good treatment of spectral elements in the lowbrow spirit of this book will have to await another volume. Perhaps it is just as well.The bibliographic explosion is merely a symptom of a field that is still rapidly evolving.The reader is invited to use this book as a base camp for his or her own expeditions. The Heart of Africa has lost its mystery;the planets of Tau Ceti are currently unknown and unreachable.Nevertheless,the rise of digital computers has given this generation its galleons and astrolabes.The undiscovered lands exist,in one sense,only as intermittent electric rivers in dendritic networks of copper and silicon,invisible as the soul.And yet the mystery of scientific computing is that its new worlds over the water,wrought only of numbers and video images,are as real as the furrowed brow of the first Cro-Magnon who was mystified by the stars,and looked for a story
Preface xiii My original plan was to build a bibliographical database on spectral methods and applications of spectral algorithms that could be printed in full here. Alas, this dream was overtaken by events: as the database grew past 2000 items, I was forced to limit the bibliography to 1025 references. Even so, this partial bibliography and the Science Citation Index should provide the reader with ample entry points into any desired topic. The complete database is available online at the author’s homepage, currently at http://wwwpersonal.engin.umich.edu/∼jpboyd. To paraphrase Newton, it is better to stand on the shoulders of giants than to try to recreate what others have already done better. Spectral elements have become an increasingly important part of the spectral world in the last decade. However, the first edition, with but a single chapter on spectral elements, was almost 800 pages long. (Students irrevently dubbed it the “Encyclopedia Boydica”.) So, I have reluctantly included only the original chapter on domain decomposition in this edition. A good treatment of spectral elements in the lowbrow spirit of this book will have to await another volume. Perhaps it is just as well. The bibliographic explosion is merely a symptom of a field that is still rapidly evolving. The reader is invited to use this book as a base camp for his or her own expeditions. The Heart of Africa has lost its mystery; the planets of Tau Ceti are currently unknown and unreachable. Nevertheless, the rise of digital computers has given this generation its galleons and astrolabes. The undiscovered lands exist, in one sense, only as intermittent electric rivers in dendritic networks of copper and silicon, invisible as the soul. And yet the mystery of scientific computing is that its new worlds over the water, wrought only of numbers and video images, are as real as the furrowed brow of the first Cro-Magnon who was mystified by the stars, and looked for a story
Acknowledgments The author's work has been supported by the National Science Foundation through the Physical Oceanography.Meteorology,Computational Engineering and Computational Math- ematics programs via grants OCE7909191,OCE8108530,OCE8305648,OCE8509923,OCE812300. DMS8716766 and by the Department of Energy.My leave of absence at Harvard in 1980 was supported through grant NASA NGL-22-007-228 and the hospitality of Richard Lindzen. My sabbatical at Rutgers was supported by the Institute for Marine and Coastal Sciences and the hospitality of Dale Haidvogel. I am grateful for the comments and suggestions of William Schultz,George Delic,and the students of the course on which this book is based,especially Ahmet Selamet,Mark Storz,Sue Haupt,Mark Schumack,Hong Ma,Beth Wingate,Laila Guessous,Natasha Flyer and Jeff Hittinger.I thank Andreas Chaniotis for correcting a formula I am also appreciative of the following publishers and authors for permission to repro- duce figures or tables.Fig.3.3:C.A.Coulson,Valence (1973),Oxford University Press. Fig.7.3:H.Weyl,Symmetry(1952)[copyright renewed,1980].Princeton University Press. Tables 9.1 and Figs.9.1 and 9.2:D.Gottlieb and S.A.Orszag.Numerical Analysis of Spectral Methods(1977),Society for Industrial and Applied Mathematics.Fig.12-4:C.Canuto and A.Quarteroni,Journal of Computational Physics(1985),Academic Press.Tables 12.2 and 12.3: T.Z.Zang,Y.S.Wong and M.Y.Hussaini,Journal of Computational Physics(1984),Academic Press.Fig.13.1 and Table 13.2:J.P.Boyd,Journal of Computational Physics(1985),Academic Press.Fig.14.3:E.Merzbacher,Quantum Mechanics(1970).John Wiley and Sons.Figs. 14.4,14.5,14.7,14.8,14.9,14.10,and 14.11:J.P.Boyd Journal of Computational Physics(1987), Academic Press.Fig.15.1:W.D'Arcy Thompson,Growth and Form(1917),Cambridge Uni- versity Press.Fig.D.1 (wth changes):J.P.Boyd,Physica D(1986),Elsevier.Fig.D.2:E. Wasserstrom,SIAM Review(1973),Society for Industrial and Applied Mathematics. I thank Gene,Dale,Dave and Terry of the Technical Illustration Dept,DRDA [now disbanded],for turning my rough graphs and schematics into camera-ready drawings. I also would like to acknowledge a debt to Paul Bamberg of the Harvard Physics de- partment.His lecturing style strongly influenced mine,especially his heavy reliance on class notes both as text and transparencies. I thank Joel Primack,who directed my undergraduate research,for his many lessons. One is the importance of preceding calculation with estimation.Another is the need to write quick-and-rough reports,summary sheets and annotations for even the most prelim- inary results.It is only too true that "otherwise,in six months all your computer output and all your algebra will seem the work of a stranger." I am also thankful for Richard Goody's willingness to humour an undergraduate by teaching him in a reading course.Our joint venture on tides in the Martian atmosphere was scooped,but I found my calling. I am grateful for Richard Lindzen's patient tolerance of my first experiments with Chebyshev polynomials.His running commentary on science,scientists,and the interplay of numerics and analysis was a treasured part of my education. xiv
Acknowledgments The author’s work has been supported by the National Science Foundation through the Physical Oceanography, Meteorology, Computational Engineering and Computational Mathematics programs via grants OCE7909191, OCE8108530, OCE8305648, OCE8509923, OCE812300, DMS8716766 and by the Department of Energy. My leave of absence at Harvard in 1980 was supported through grant NASA NGL-22-007-228 and the hospitality of Richard Lindzen. My sabbatical at Rutgers was supported by the Institute for Marine and Coastal Sciences and the hospitality of Dale Haidvogel. I am grateful for the comments and suggestions of William Schultz, George Delic, and the students of the course on which this book is based, especially Ahmet Selamet, Mark Storz, Sue Haupt, Mark Schumack, Hong Ma, Beth Wingate, Laila Guessous, Natasha Flyer and Jeff Hittinger. I thank Andreas Chaniotis for correcting a formula I am also appreciative of the following publishers and authors for permission to reproduce figures or tables. Fig. 3.3: C. A. Coulson, Valence (1973), Oxford University Press. Fig. 7.3: H. Weyl, Symmetry (1952) [copyright renewed, 1980], Princeton University Press. Tables 9.1 and Figs. 9.1 and 9.2: D. Gottlieb and S. A. Orszag, Numerical Analysis of Spectral Methods (1977), Society for Industrial and Applied Mathematics. Fig. 12-4: C. Canuto and A. Quarteroni, Journal of Computational Physics (1985), Academic Press. Tables 12.2 and 12.3: T. Z. Zang, Y. S. Wong and M. Y. Hussaini, Journal of Computational Physics (1984), Academic Press. Fig. 13.1 and Table 13.2: J. P. Boyd, Journal of Computational Physics (1985), Academic Press. Fig. 14.3: E. Merzbacher, Quantum Mechanics (1970), John Wiley and Sons. Figs. 14.4, 14.5, 14.7, 14.8, 14.9, 14.10, and 14.11: J. P. Boyd Journal of Computational Physics (1987), Academic Press. Fig. 15.1: W. D’Arcy Thompson, Growth and Form (1917), Cambridge University Press. Fig. D.1 (wth changes): J. P. Boyd, Physica D (1986), Elsevier. Fig. D.2: E. Wasserstrom, SIAM Review (1973), Society for Industrial and Applied Mathematics. I thank Gene, Dale, Dave and Terry of the Technical Illustration Dept., DRDA [now disbanded], for turning my rough graphs and schematics into camera-ready drawings. I also would like to acknowledge a debt to Paul Bamberg of the Harvard Physics department. His lecturing style strongly influenced mine, especially his heavy reliance on class notes both as text and transparencies. I thank Joel Primack, who directed my undergraduate research, for his many lessons. One is the importance of preceding calculation with estimation. Another is the need to write quick-and-rough reports, summary sheets and annotations for even the most preliminary results. It is only too true that “otherwise, in six months all your computer output and all your algebra will seem the work of a stranger.” I am also thankful for Richard Goody’s willingness to humour an undergraduate by teaching him in a reading course. Our joint venture on tides in the Martian atmosphere was scooped, but I found my calling. I am grateful for Richard Lindzen’s patient tolerance of my first experiments with Chebyshev polynomials. His running commentary on science, scientists, and the interplay of numerics and analysis was a treasured part of my education. xiv
Acknowledgments XV I thank Steven Orszag for accepting this manuscript for the Lecture Notes in Engi- neering series (Springer-Verlag)where the first edition appeared.The treatment of time- stepping methods in Chapter 10 is heavily influenced by his MIT lectures of many years ago,and the whole book is strongly shaped by his many contributions to the field. I am appreciative of John Grafton and the staff of Dover Press for bringing this book back into print in an expanded and corrected form. Lastly,I am grateful for the support of the colleagues and staff of the University of Michigan,particularly Stan Jacobs for sharing his knowledge of nonlinear waves and per- turbation theory,Bill Schultz for many fruitful collaborations in applying spectral methods to mechanical engineering,and Bill Kuhn for allowing me to introduce the course on which this book is based
Acknowledgments xv I thank Steven Orszag for accepting this manuscript for the Lecture Notes in Engineering series (Springer-Verlag) where the first edition appeared. The treatment of timestepping methods in Chapter 10 is heavily influenced by his MIT lectures of many years ago, and the whole book is strongly shaped by his many contributions to the field. I am appreciative of John Grafton and the staff of Dover Press for bringing this book back into print in an expanded and corrected form. Lastly, I am grateful for the support of the colleagues and staff of the University of Michigan, particularly Stan Jacobs for sharing his knowledge of nonlinear waves and perturbation theory, Bill Schultz for many fruitful collaborations in applying spectral methods to mechanical engineering, and Bill Kuhn for allowing me to introduce the course on which this book is based