ITERATIVE METHODS FOR SINGULAR LINEAR EQUATIONS AND LEAST-SQUARES PROBLEMS A DISSERTATION SUBMITTED TO THE PROGRAM IN COMPUTATIONAL AND MATHEMATICAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Sou-Cheng (Terrya) Choi December 2006 UMI Number: 3242533 Copyright 2007 by Choi, Sou-Cheng (Terrya) All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3242533 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Copyright @ 2007 by Sou-Cheng (Terrya) Choi All Rights Reserved I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Saunders) Principal Advisor I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Aut Abel (Gene H.
Golub) Co-Advisor I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Larsen) I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of < z2zzz _ je. (Doronấy)” s4 Approved for the University Committee on Graduate Studies. Abstract CG, MINRES, and SYMMLQ are Krylov subspace methods for solving large symmetric systems of linear equations.
CG (the conjugate-gradient method) is reliable on positive-definite systems, while MINRES and SYMMLQ are designed for indefinite systems. When these methods are applied to an inconsistent system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ’s solution could explode, while MINRES would give a least- squares solution but not necessarily the minimum-length solution (often called the pseudoinverse solution). This understanding motivates us to design a MINRES-like algorithm to compute minimum-length solutions to singular symmetric systems. MINRES uses QR factors of the tridiagonal matrix from the Lanczos process (where R is upper-tridiagonal).
Our algorithm uses a QLP decomposition (where rotations on the right reduce R to lower-tridiagonal form), and so we call it MINRES-QLP. On singular or nonsingular systems, MINRES-QLP can give more accurate solutions than MINRES or SYMMLQ. We derive preconditioned MINRES-QLP, new stopping rules, and better estimates of the solution and residual norms, the matrix norm and condition number. For a singular matrix of arbitrary shape, we observe that null vectors can be obtained by solving least-squares problems involving the transpose of the matrix.
For sparse rectangular matrices, this suggests an application of the iterative solver LSQR. In the square case, MINRES, MINRES-QLP, or LSQR are applicable. Results are given for solving homogeneous systems, computing the stationary probability vector for Markov Chain models, and finding null vectors for sparse systems arising in helioseismology. Acknowledgments First and foremost, I owe an enormous debt of gratitude to my advisor Professor Michael Saunders for his tireless support throughout my graduate education in Stanford.
Michael is the best mentor a research student could possibly hope for. He is of course an amazing academic going by his first-rate scholarly abilities, unparalleled mastery of his specialty, and profound insights on matters algorithmic and numerical (not surprising considering that he is one of most highly cited computer scientists in the world today). But above and beyond all these, Michael is a most wonderful gentleman with great human qualities—he is modest, compassionate, understanding, accommodating, and possesses a witty sense of humor. I am very fortunate, very proud, and very honored to be Michael’s student.
This thesis certainly would not have been completed without Michael’s most meticulous and thorough revision. Professor Gene Golub is a demigod in our field and a driving force behind the computational mathematics community at Stanford. Incidentally, Gene is also Michael’s advisor many years ago. I am also very grateful to Gene for his generosity and encouragement.
He is the only professor I know who gives students 24-hour access to his large collection of books in his office. His stature and renown for hospitality attract visiting researchers from all over the world and create a most lively and dynamic environment at Stanford. This contributed greatly to my academic development. Like me, Gene came from a working class family—a rarity in a place like Stanford where many students are of the well-heeled gentry.
He has often reminded me that a humble background is no obstacle to success. I am also very fortunate, very proud, and very honored to have Gene as my co-advisor. Special thanks are due to Professor Chris Paige Of McGill University for generously sharing his ideas and insights. He spent many precious hours with me over emails and long discussions during his two visits to Stanford in the past year.
Chris is a giant in the field and is a great honour to fill a gap in one of the famous works of Chris and Michael started long ago. I thank my reading committee members: Professor Doron Levy and Dr. Their helpful suggestions have improved this thesis enormously. My thanks also to Professor Jerome Friedman for chairing my oral defense despite already having retired a few months earlier.
I am very grateful to my professors from the National University of Singapore (NUS), who have instilled and inspired in me interests in computational mathematics since I was an under- graduate: Dr. Ma, Professors Choy-Heng Lai, Jiang-Sheng Wang, Zuowei Shen, Gongyun Zhou, Kim-Chuan Toh, Belal Baaquie, Kan Chen, and last but not least Prabir Burman (UC Davis). The work in this thesis was generously supported by research grants of Professors Michael Saunders, Gene Golub, and David Donoho. Thanks are also due to the C.
Gary & Virginia Skartvedt Endowed Engineering Fund for a Stanford School-of-Engineering Fellowship, and to the Silicon Valley Engineering Council for an SVEC Scholarship. MATLAB has been an indispensable tool—without which, none of the numerical experiments could have been performed with such ease and efficiency. I am proud to say that I learnt MATLAB first-hand from the person who created it—Professor Cleve Moler. I thank Cleve for selecting me as his teaching assistant for the course on which his very enjoyable book [71] is based (and for kindly recommending me as teaching assistant to his daughter Professor Kathryn Moler, who taught the course in the subsequent year).
The book is filled with illuminating examples and this thesis has borrowed a most fascinating one (cf. I thank Michael Friedlander for the elegant thesis template that he generously shares with the Stanford public. I have been fortunate to intern at both Google and IBM Almaden Labs, during which periods I benefited from working with Doctors John Tomlin, Andrew Tomkins, and Tom Truong. Specifically I want to thank Dr.
Xiaoye Sherry Li and Dr. Amy Langville for inviting me to speak about applications motivated by this thesis in Lawrence Berkeley Lab and the SIAM Annual Meeting 2004 respectively. Thanks also to Professor Beresford Parlett and Professor Inderjit Dhillon for the opportunities to speak in their seminars in UC Berkeley and UT Austin respectively. I also want to take the opportunity to thank each administrator and staff members of Stanford and NUS who have gone beyond their duties of call: Professors Walter Murray and Peter Glynn, Indira Choudhury, Lilian Lao, Evelyn Boughton, Lorrie Papadakis, Tim Keely, Seth Tornborg, Suzanne Bigas, Connie Chan, Christine Fiksdal, Dana Halpin, Jam Kiattinant, Nikkie Salgado, Claire Stager, Deborah Michael, Lori Cottle, Pat Shallenberger, Helen Tombropoulos, Sharon Bergman, Lee Kuen Chee, and Kowk Te Ang.
I am indebted to the following friends and colleagues for their friendship and encouragement that made my Stanford years so much more enjoyable: Michael’s family Prue, Tania, and Emily; David, Ha, and baby Mike Saunders; Holly Jin, Neil, Danlin, and Hansen Lillemark; Lilian Lao, Michael and Victor Dang; Justin Wing Lok Wan and Winnie Wan Chu; Dulce Ponceleón, Walter, Emma and Sofia Murray; Von Bing Yap and Anne Suet Lin Chong; Pei Yee Woo and Kenneth Wee; Larry and Mary Wong. I thank for their friendship and wisdom: Monica Johnston, Wanchi So, Regina Ip-Lau, Stephen Ng, Wah Tung Lau, Chris Ng, Jonathan Choi, Xiaoqing Zhu, Sorav Bansal, Jeonghee Yi, Mike Ching, Cindy Law, Doris Wong, Jasmine Wong, Sandi Suardi, Sharon Wong, Popoh Low, Grace Ng, Roland Law, Ricky Ip, Fanny Lau, Stephen Yeung, Kenneth (D&G) Wong Chok Hang Yeung, Carrie Teng, Grace Hui, Anthony So, Samuel Ieong, Kenneth Tam, Yee Wai Chong, Anthony Fai Tong Chung, Winnie Wing Yin Choi, Victor Lee, William Yu Cheong Chan, Dik Kin Wong, Collin Kwok-Leung Mui, Rosanna Man, Michael Friedlander, Kaustuv, Zheng Su, Yen Lin Chia, Hanh Huynh, Wanjun Mi, Linzhong Deng, Ofer Levi, James Lambers, Paul Tupper, Melissa Aczon, Steve Bryson, Oren Livne, Valentin Spitkovsky, Cindy Mason, Morten Mørup, Anil Gaba, Donald van Deventer, Kenji Imai, Chong-Peng Toh, Frederick Willeboordse, Yuan Ping Feng, Alex Ling, Roland Su, Helen Lau, and Suzanne Woo. I have been infinitely lucky to have met Lek-Heng Lim when we were both undergraduates in NUS. As I made further acquaintance with Lek-Heng, I found him among the most thoughtful, encouraging, and inspiring person of all friends and colleagues.
Without his encouragement, I would not have started this long journey, let alone finished. Last but not least, I thank my parents and grandma for years of toiling and putting up with my “life-long” studies. I am indebted to my siblings Dawn and Stephen, and brother-in-law Jack Cheng for their constant support. vi Contents List of Tables and Figures xiii Introduction CBON©FHo 1 1.1 The Motivating Problem.
0c cee ee ee kia 1. HQ nà nà KV V Và va 1. Q Q Q HQ ee k k k k ka 113 SymmetricSystems. Q0 HQ HH ee va 1.
Q Q Q Q HQ HH HQ nu ng k ko kh K k ky 1.21 Problem Description and Formal Solutions .2 Existing Numerical Algorithms. 00 ee eee eee 1.3 Background for MINRES. 0 eee eee eee 1. ee es aCOCCee 2 Existing Iterative Methods for Hermitian Problems 13 2.1 The Lanczos Process.2 Lanczos-Based Methods for Linear Systems .0 eee ee ees 16 22.
Existing Iterative Methods for Hermitian Least-Squares .4 Stopping Conditions and Norm Estimates .1 Residual and Residual Norm. 2 ee ee ee 36 2.5 Matrix Condition Numbers — 40 3 MINRES-QLP 3.11 Effects of Rounding ErrorsinMINRES.2 Existing Approaches to Solving Hermitian Least-Squares .3 Orthogonal Matrix Decompositions for Singular Matrices. vii 32 MINRBS-QLP. QC LH HQ Q nu nu cà vn V V V kg kia 3.1 The MINRES-QLP Subproblem .2 Solving the Subproblem.0000 eee eee La 3.4 Transfer from MINRES to MINRES-QLP.3 Stopping Conditions and Norm Estimates .1 Residual and Residual Norm.
2 eee ee ee 3.0 cc Q v Ty kg vn kg kg kg va 3. Q Q Q k LH gu Q v kg ki v kia 3.4 Matrix Condition Numbers. eee ee ee es 3.6 Projection of Right-hand Side onto Krylov Subspaces .4 Preconditioned MINRES and MINRES-QLP. De ee ee ee 3.
ch ng vn quà gà v ki kia 3.2 Preconditioning Singular lz=bÙb. ee ee ee ee 3.3 Preconditioning Singular Arb 2. cu cu kg 3.3 Incomplete Cholesky Factorization. 000048 Numerical Experiments on Symmetric Systems 41 A Singular Indefinite System ©.
ee ee 42 Two Laplacian Systems .