ITERATIVE METHODS FOR SINGULAR LINEAR EQUATIONS AND LEAST-SQUARES PROBLEMS

Luận án Tiến sĩ về phương pháp lặp giải phương trình tuyến tính suy biến và bài toán bình phương tối thiểu. Nghiên cứu chuyên sâu, phân tích thuật toán hiệu quả.

• Tác giả: Sou-Cheng (Terrya) Choi
• Người hướng dẫn: Professor Michael Saunders
• Trường học: Stanford University
• Chuyên ngành: Computational and Mathematical Engineering
• Đề tài: Iterative Methods For Singular Linear Equations And Least-Squares Problems
• Loại tài liệu: Luận án Tiến sĩ
• Năm xuất bản: 2007
• Địa điểm: Ann Arbor, MI

Tóm tắt

I. Tổng Quan Giải Thuật Lặp Cho Phương Trình Tuyến Tính Suy Biến

Luận án tiến sĩ này tập trung vào việc nghiên cứu và phát triển các giải thuật lặp hiệu quả để giải quyết phương trình tuyến tính suy biến và bài toán bình phương tối thiểu. Đây là những vấn đề quan trọng trong nhiều lĩnh vực khoa học kỹ thuật, từ xử lý ảnh đến mô hình hóa tài chính. Luận án này khám phá các phương pháp lặp hiện có, xác định những hạn chế của chúng và đề xuất các giải pháp mới, đặc biệt là trong việc xử lý các ma trận suy biến. Nghiên cứu này đóng góp vào việc cải thiện độ chính xác và hiệu quả của các thuật toán số, mang lại những ứng dụng thực tiễn quan trọng. Cụ thể, luận án này đề xuất một thuật toán MINRES-QLP mới, hứa hẹn mang lại kết quả tốt hơn so với các phương pháp truyền thống.

1.1. Động Lực Bài Toán Xếp Hạng Trang Web Của Google

Bài toán PageRank của Google vào năm 1998, với khoảng 150 triệu trang web, đã thúc đẩy việc sử dụng phương pháp lặp để tính toán vectơ riêng của ma trận liên kết. Đến năm 2003, số lượng trang web tăng lên 2 tỷ, và phương pháp lặp vẫn được sử dụng hàng tháng để cập nhật xếp hạng. Ma trận A đại diện cho liên kết giữa các trang web, và lý thuyết Perron-Frobenius đảm bảo sự hội tụ của phương pháp lặp. Số lượng vòng lặp yêu cầu (kp) thường chỉ vài trăm. Bài toán này đã khơi gợi sự quan tâm đến việc sử dụng các phương pháp không gian Krylov thay thế cho phương pháp lũy thừa.

1.2. Giải Pháp Sử Dụng LSQR Để Tính Toán Các Vectơ Vô Hiệu

Luận án này mở rộng phạm vi nghiên cứu sang các hệ phương trình tuyến tính suy biến không đối xứng. Cụ thể, giải thuật LSQR được sử dụng để tính toán các vectơ vô hiệu của ma trận A. Vấn đề được đặt ra là liệu LSQR có thể tìm ra nghiệm có độ dài nhỏ nhất hay không. Nghiên cứu nhận thấy rằng, với các quy tắc dừng thông thường, LSQR hội tụ đến một nghiệm bình phương tối thiểu không có chuẩn lớn, do đó không phải là vectơ của A. Để có được vectơ, cần phải vô hiệu hóa các điều kiện dừng để LSQR tiếp tục lặp cho đến khi chuẩn của nghiệm tăng lên.

II. Thách Thức Giải Pháp Cho Phương Trình Tuyến Tính Suy Biến

Việc giải phương trình tuyến tính suy biến và bài toán bình phương tối thiểu đặt ra nhiều thách thức. Các phương pháp truyền thống có thể không hội tụ hoặc cho kết quả không chính xác, đặc biệt khi ma trận hệ số có điều kiện kém (ill-conditioned systems). Luận án này đi sâu vào phân tích những khó khăn này và đề xuất các giải thuật lặp mới để khắc phục chúng. Nghiên cứu tập trung vào việc cải thiện độ ổn định và độ chính xác của giải thuật, đồng thời giảm thiểu chi phí tính toán. Việc hiểu rõ các tính chất của ma trận suy biến và các yếu tố ảnh hưởng đến độ hội tụ của giải thuật là chìa khóa để giải quyết vấn đề này. Cần phải xem xét đến sai số làm tròn và việc sử dụng các kỹ thuật chính quy hóa.

2.1. Bài Toán Nghiệm Độ Dài Ngắn Nhất Với LSQR Khi Ma Trận Suy Biến

Một câu hỏi quan trọng được đặt ra: LSQR đang hội tụ đến giải pháp nào khi A suy biến với các quy tắc dừng thông thường? Câu trả lời có lẽ là nghiệm có độ dài nhỏ nhất, tức là giải pháp tối thiểu hóa |x|| trong số các giải pháp tối thiểu hóa ||Ax-b||. Trong trường hợp này, vectơ r = b - Ax thỏa mãn Aᵀr = 0. Nghiên cứu nhận ra rằng LSQR đang tính toán vectơ vô hiệu của ma trận chuyển vị Aᵀ. Điều này dẫn đến một phương pháp mới để tìm vectơ của ma trận suy biến A bằng cách giải bài toán bình phương tối thiểu min ||Aᵀy-c||₂.

2.2. Giải Quyết Vectơ Đối Xứng Qua MINRES Trong Bài Toán Bình Phương Tối Thiểu

Trong trường hợp đối xứng, cả hai hệ min ||Ax-b||₂ và min ||Aᵀy-c||₂ có dạng tương tự. Với ma trận A đối xứng, các phương pháp không gian Krylov tự nhiên là SYMMLQ và MINRES. Khi A suy biến, MINRES được ưu tiên do cho phép số dư r = b - Ax khác không. Trong bài toán bình phương tối thiểu, r có thể khác không, vì vậy cần các điều kiện dừng mới để phát hiện khi ||Aᵀr|| hoặc ||r|| đủ nhỏ. Nghiên cứu phát triển các công thức đệ quy ước lượng chính xác ||Az|| và ||Aᵀr|| mà không cần thêm phép nhân ma trận-vectơ.

III. Phương Pháp MINRES QLP Cho Hệ Tuyến Tính Suy Biến

Luận án này giới thiệu một phương pháp mới dựa trên MINRES, được gọi là MINRES-QLP. Phương pháp này sử dụng phân tích QLP thay vì QR để giải quyết bài toán con bình phương tối thiểu. MINRES-QLP hứa hẹn mang lại kết quả chính xác hơn so với MINRES và SYMMLQ, đặc biệt trong trường hợp hệ phương trình tuyến tính suy biến. Nghiên cứu này cũng trình bày các kỹ thuật tiền điều kiện (preconditioning) cho MINRES-QLP, giúp cải thiện hiệu suất và độ ổn định của giải thuật. Các ước tính mới về chuẩn nghiệm và chuẩn số dư cũng được phát triển để cải thiện việc dừng giải thuật.

3.1. MINRES QLP Phân Tích Lỗi Làm Tròn Trong Giải Pháp

Luận án xem xét phân tích lỗi làm tròn của MINRES-QLP. Các kết quả thực nghiệm cho thấy MINRES-QLP có thể cho kết quả chính xác hơn MINRES hoặc SYMMLQ trên các hệ phương trình suy biến hoặc không suy biến. Điều này nhờ vào việc sử dụng phân tích QLP, giúp giảm ảnh hưởng của lỗi làm tròn. Các giải thuật hiện tại thường chỉ xem xét lỗi làm tròn trên các hệ Hermitian, trong khi MINRES-QLP tập trung vào các hệ suy biến, một khía cạnh ít được khám phá.

3.2. Tiền Xử Lý MINRES và MINRES QLP Cải Thiện Tốc Độ Hội Tụ

Luận án đề xuất các kỹ thuật tiền xử lý cho MINRES và MINRES-QLP để cải thiện tốc độ hội tụ của giải thuật trong các hệ suy biến. Các phương pháp tiền xử lý bao gồm tiền xử lý đường chéo, chuẩn hóa hai lần và phân tích Cholesky không đầy đủ. Việc lựa chọn phương pháp tiền xử lý phù hợp phụ thuộc vào đặc điểm của ma trận hệ số. Các kết quả thực nghiệm cho thấy việc sử dụng tiền xử lý có thể giảm đáng kể số lượng vòng lặp cần thiết để đạt được độ chính xác mong muốn.

IV. Ứng Dụng Tính Toán Vectơ Vô Hiệu Trong Các Bài Toán Thực Tế

Luận án này khám phá các ứng dụng của giải thuật lặp trong việc tính toán vectơ vô hiệu, vectơ riêng và vectơ kỳ dị. Các ứng dụng bao gồm giải bài toán giá trị riêng, bài toán giá trị kỳ dị, và các bài toán giá trị riêng tổng quát. Đặc biệt, nghiên cứu này tập trung vào việc tính toán vectơ vô hiệu trong các hệ phương trình phát sinh từ các mô hình chuỗi Markov và các bài toán trong Nhật động học (helioseismology). Các kết quả thực nghiệm chứng minh tính hiệu quả của giải thuật được đề xuất trong các ứng dụng thực tế.

4.1. PageRank Giải Bài Toán Xếp Hạng Trang Web Bằng LSQR

Luận án xem xét ứng dụng của LSQR trong bài toán PageRank. Với ma trận A không đối xứng, bài toán trở thành việc tìm vectơ riêng của ma trận Google. Các kết quả thực nghiệm cho thấy LSQR có thể hội tụ nhanh chóng đến vectơ PageRank, đặc biệt khi sử dụng các kỹ thuật tiền xử lý. So sánh với phương pháp lũy thừa truyền thống, LSQR cung cấp một giải pháp thay thế hiệu quả, đặc biệt trong các trường hợp ma trận lớn và thưa.

4.2. Nhật Động Học Vectơ Vô Hiệu Đa Chiều Từ Nghiên Cứu Thống Kê

Luận án khám phá việc tính toán vectơ vô hiệu đa chiều trong các bài toán phát sinh từ Nhật động học. Trong lĩnh vực này, việc tìm kiếm các vectơ thỏa mãn các điều kiện nhất định rất quan trọng. Nghiên cứu đề xuất một giải thuật mới, MLSQRunull, để tính toán nhiều vectơ trực giao, đáp ứng các yêu cầu cụ thể của bài toán. Các kết quả thực nghiệm chứng minh tính hiệu quả của MLSQRunull trong việc giải quyết các bài toán phức tạp trong Nhật động học.

V. Kết Luận Tối Ưu Giải Thuật Lặp Cho Tương Lai Nghiên Cứu

Luận án này đã đóng góp vào việc phát triển các giải thuật lặp hiệu quả hơn cho việc giải quyết phương trình tuyến tính suy biến và bài toán bình phương tối thiểu. MINRES-QLP là một cải tiến đáng kể so với các phương pháp truyền thống, đặc biệt trong các trường hợp ma trận có điều kiện kém. Các kỹ thuật tiền xử lý và các ước tính mới về chuẩn nghiệm và chuẩn số dư cũng góp phần nâng cao hiệu suất và độ tin cậy của giải thuật. Nghiên cứu này mở ra những hướng đi mới cho các nghiên cứu trong tương lai, bao gồm việc mở rộng MINRES-QLP cho các hệ phương trình phi tuyến tính và việc phát triển các giải thuật song song để giải quyết các bài toán quy mô lớn.

5.1. Tóm Lược Ứng Dụng Thực Tế Của Phương Pháp MINRES QLP

Luận án trình bày MINRES-QLP, một giải thuật cải tiến cho các hệ tuyến tính suy biến và các bài toán bình phương tối thiểu. MINRES-QLP sử dụng phân tích QLP thay vì QR, cung cấp giải pháp chính xác hơn. Các cải tiến bao gồm các điều kiện dừng mới, ước tính chuẩn tốt hơn và các kỹ thuật tiền xử lý hiệu quả. Các kết quả thực nghiệm chứng minh tính hiệu quả của MINRES-QLP trong các ứng dụng thực tế như xếp hạng trang web và phân tích dữ liệu thiên văn.

5.2. Hướng Đi Tương Lai Nghiên Cứu Sâu Hơn Về Giải Thuật Lặp

Luận án đề xuất một số hướng đi cho các nghiên cứu trong tương lai. Cần phát triển các giải thuật lặp mạnh mẽ hơn cho các hệ tuyến tính quy mô lớn và các bài toán bình phương tối thiểu có ràng buộc. Việc nghiên cứu các kỹ thuật tiền xử lý mới và các phương pháp chính quy hóa tiên tiến cũng rất quan trọng. Cuối cùng, việc phát triển các giải thuật lặp song song và phân tán sẽ cho phép giải quyết các bài toán phức tạp hơn trong nhiều lĩnh vực khoa học và kỹ thuật.

Trích đoạn nội dung tài liệu

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 .