Author: Anne Greenbaum
Category: Equations, Simultaneous
Much recent research has concentrated on the efficient solution of large sparse or structured linear systems using iterative methods. A language loaded with acronyms for a thousand different algorithms has developed, and it is often difficult even for specialists to identify the basic principles involved. Here is a book that focuses on the analysis of iterative methods. The author includes the most useful algorithms from a practical point of view and discusses the mathematical principles behind their derivation and analysis. Several questions are emphasized throughout: Does the method converge? If so, how fast? Is it optimal, among a certain class? If not, can it be shown to be near-optimal? The answers are presented clearly, when they are known, and remaining important open questions are laid out for further study. Greenbaum includes important material on the effect of rounding errors on iterative methods that has not appeared in other books on this subject. Additional important topics include a discussion of the open problem of finding a provably near-optimal short recurrence for non-Hermitian linear systems; the relation of matrix properties such as the field of values and the pseudospectrum to the convergence rate of iterative methods; comparison theorems for preconditioners and discussion of optimal preconditioners of specified forms; introductory material on the analysis of incomplete Cholesky, multigrid, and domain decomposition preconditioners, using the diffusion equation and the neutron transport equation as example problems. A small set of recommended algorithms and implementations is included.
Author: Yousef Saad
Mathematics of Computing -- General.
Author: Clarence Edgar Lee,P. M. Stone
Category: Differential equations, Elliptic
Iterative numerical methods for solving independent, simultaneous, inhomogeneous linear equations are surveyed. Application of the methods to elliptic difference equations as arise in neutron diffasion, heat conduction, and potential problems is discussed.
Building Blocks for Iterative Methods
Author: Richard Barrett,Michael W. Berry,Tony F. Chan,James Demmel,June Donato,Jack Dongarra,Victor Eijkhout,Roldan Pozo,Charles Romine,Henk van der Vorst
In this book, which focuses on the use of iterative methods for solving large sparse systems of linear equations, templates are introduced to meet the needs of both the traditional user and the high-performance specialist. Templates, a description of a general algorithm rather than the executable object or source code more commonly found in a conventional software library, offer whatever degree of customization the user may desire. Templates offer three distinct advantages: they are general and reusable; they are not language specific; and they exploit the expertise of both the numerical analyst, who creates a template reflecting in-depth knowledge of a specific numerical technique, and the computational scientist, who then provides "value-added" capability to the general template description, customizing it for specific needs. For each template that is presented, the authors provide: a mathematical description of the flow of algorithm; discussion of convergence and stopping criteria to use in the iteration; suggestions for applying a method to special matrix types; advice for tuning the template; tips on parallel implementations; and hints as to when and why a method is useful.
Author: C. T. Kelley
Mathematics of Computing -- Numerical Analysis.
Author: David R. Kincaid,Linda J. Hayes
Publisher: Academic Press
Iterative Methods for Large Linear Systems contains a wide spectrum of research topics related to iterative methods, such as searching for optimum parameters, using hierarchical basis preconditioners, utilizing software as a research tool, and developing algorithms for vector and parallel computers. This book provides an overview of the use of iterative methods for solving sparse linear systems, identifying future research directions in the mainstream of modern scientific computing with an eye to contributions of the past, present, and future. Different iterative algorithms that include the successive overrelaxation (SOR) method, symmetric and unsymmetric SOR methods, local (ad-hoc) SOR scheme, and alternating direction implicit (ADI) method are also discussed. This text likewise covers the block iterative methods, asynchronous iterative procedures, multilevel methods, adaptive algorithms, and domain decomposition algorithms. This publication is a good source for mathematicians and computer scientists interested in iterative methods for large linear systems.
Author: Gerard Meurant
This book deals with numerical methods for solving large sparse linear systems of equations, particularly those arising from the discretization of partial differential equations. It covers both direct and iterative methods. Direct methods which are considered are variants of Gaussian elimination and fast solvers for separable partial differential equations in rectangular domains. The book reviews the classical iterative methods like Jacobi, Gauss-Seidel and alternating directions algorithms. A particular emphasis is put on the conjugate gradient as well as conjugate gradient -like methods for non symmetric problems. Most efficient preconditioners used to speed up convergence are studied. A chapter is devoted to the multigrid method and the book ends with domain decomposition algorithms that are well suited for solving linear systems on parallel computers.
Author: Michael K. Ng
Publisher: Oxford University Press, USA
Toeplitz and Toeplitz-related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. This book deals primarily with iterative methods for solving Toeplitz and Toeplitz-related linear systems, discussing both the algorithms and their convergence theories. A basic knowledge of real analysis, elementary numerical analysis and linear algebra is assumed. The first part of the book (chapters one and two) gives a brief review of some terms and results in linear algebra and the conjugate gradient method, which are important topics for handling the mathematics later on in the book. The second part of the book (chapters three to seven) presents the theory of using iterative methods for solving Toeplitz and Toeplitz-related systems. The third part of the book (chapters eight to twelve) presents recent results from applying the use of iterative methods in different fields of applications, such as partial differential equations, signal and image processing, integral equations and queuing networks. These chapters provide research and application-oriented readers with a thorough understanding of using iterative methods, enabling them not only to apply these methods to the problems discussed but also to derive and analyse new methods for other types of problems and applications.
Author: J. F. Traub
Publisher: American Mathematical Soc.
From the Preface (1964): ``This book presents a general theory of iteration algorithms for the numerical solution of equations and systems of equations. The relationship between the quantity and the quality of information used by an algorithm and the efficiency of the algorithm is investigated. Iteration functions are divided into four classes depending on whether they use new information at one or at several points and whether or not they reuse old information. Known iteration functions are systematized and new classes of computationally effective iteration functions are introduced. Our interest in the efficient use of information is influenced by the widespread use of computing machines ... The mathematical foundations of our subject are treated with rigor, but rigor in itself is not the main object. Some of the material is of wider application ... Most of the material is new and unpublished. Every attempt has been made to keep the subject in proper historical perspective ... ''
Author: David M. Young
Iterative Solution of Large Linear Systems describes the systematic development of a substantial portion of the theory of iterative methods for solving large linear systems, with emphasis on practical techniques. The focal point of the book is an analysis of the convergence properties of the successive overrelaxation (SOR) method as applied to a linear system where the matrix is "consistently ordered". Comprised of 18 chapters, this volume begins by showing how the solution of a certain partial differential equation by finite difference methods leads to a large linear system with a sparse matrix. The next chapter reviews matrix theory and the properties of matrices, as well as several theorems of matrix theory without proof. A number of iterative methods, including the SOR method, are then considered. Convergence theorems are also given for various iterative methods under certain assumptions on the matrix A of the system. Subsequent chapters deal with the eigenvalues of the SOR method for consistently ordered matrices; the optimum relaxation factor; nonstationary linear iterative methods; and semi-iterative methods. This book will be of interest to students and practitioners in the fields of computer science and applied mathematics.
Author: Bernd Fischer
Originally published: Chichester; New York: Wiley; Stuttgart: Teubner, c1996.
Category: Technology & Engineering
Author: Rizwan Butt
Publisher: Jones & Bartlett Learning
Part of the new Digital Filmmaker Series! Digital Filmmaking: An Introductionis the first book in the newDigital Filmmaker Series. Designed for an introductory level course in digital filmmaking, it is intended for anyone who has an interest in telling stories with pictures and sound and won't assume any familiarity with equipment or concepts on the part of the student. In addition to the basics of shooting and editing, different story forms are introduced from documentary and live events through fictional narratives. Each of the topics is covered in enough depth to allow anyone with a camera and a computer to begin creating visual projects of quality.
Theory and Applications
Author: Maxim A. Olshanskii,Eugene E. Tyrtshnikov
Iterative Methods for Linear Systems offers a mathematically rigorous introduction to fundamental iterative methods for systems of linear algebraic equations. The book distinguishes itself from other texts on the topic by providing a straightforward yet comprehensive analysis of the Krylov subspace methods, approaching the development and analysis of algorithms from various algorithmic and mathematical perspectives, and going beyond the standard description of iterative methods by connecting them in a natural way to the idea of preconditioning.
Author: Zlatko Drmac,Vjeran Hari,Luka Sopta,Zvonimir Tutek,Kresimir Veselic
Publisher: Springer Science & Business Media
Proceedings of the second conference on Applied Mathematics and Scientific Computing, held June 4-9, 2001 in Dubrovnik, Croatia. The main idea of the conference was to bring together applied mathematicians both from outside academia, as well as experts from other areas (engineering, applied sciences) whose work involves advanced mathematical techniques. During the meeting there were one complete mini-course, invited presentations, contributed talks and software presentations. A mini-course Schwarz Methods for Partial Differential Equations was given by Prof Marcus Sarkis (Worcester Polytechnic Institute, USA), and invited presentations were given by active researchers from the fields of numerical linear algebra, computational fluid dynamics , matrix theory and mathematical physics (fluid mechanics and elasticity). This volume contains the mini-course and review papers by invited speakers (Part I), as well as selected contributed presentations from the field of analysis, numerical mathematics, and engineering applications.
Author: Holger Wendland
Publisher: Cambridge University Press
This self-contained introduction to numerical linear algebra provides a comprehensive, yet concise, overview of the subject. It includes standard material such as direct methods for solving linear systems and least-squares problems, error, stability and conditioning, basic iterative methods and the calculation of eigenvalues. Later chapters cover more advanced material, such as Krylov subspace methods, multigrid methods, domain decomposition methods, multipole expansions, hierarchical matrices and compressed sensing. The book provides rigorous mathematical proofs throughout, and gives algorithms in general-purpose language-independent form. Requiring only a solid knowledge in linear algebra and basic analysis, this book will be useful for applied mathematicians, engineers, computer scientists, and all those interested in efficiently solving linear problems.
Author: Jacques Tagoudjeu
This thesis focuses on iterative methods for the treatment of the steady state neutron transport equation in slab geometry, bounded convex domain of Rn (n = 2,3) and in 1-D spherical geometry. We introduce a generic Alternate Direction Implicit (ADI)-like iterative method based on positive definite and m-accretive splitting (PAS) for linear operator equations with operators admitting such splitting. This method converges unconditionally and its SOR acceleration yields convergence results similar to those obtained in presence of finite dimensional systems with matrices possessing the Young property A. The proposed methods are illustrated by a numerical example in which an integro-differential problem of transport theory is considered. In the particular case where the positive definite part of the linear equation operator is self-adjoint, an upper bound for the contraction factor of the iterative method, which depends solely on the spectrum of the self-adjoint part is derived. As such, this method has been successfully applied to the neutron transport equation in slab and 2-D cartesian geometry and in 1-D spherical geometry. The self-adjoint and m-accretive splitting leads to a fixed point problem where the operator is a 2 by 2 matrix of operators. An infinite dimensional adaptation of minimal residual and preconditioned minimal residual algorithms using Gauss-Seidel, symmetric Gauss-Seidel and polynomial preconditioning are then applied to solve the matrix operator equation. Theoretical analysis shows that the methods converge unconditionally and upper bounds of the rate of residual decreasing which depend solely on the spectrum of the self-adjoint part of the operator are derived. The convergence of theses solvers is illustrated numerically on a sample neutron transport problem in 2-D geometry. Various test cases, including pure scattering and optically thick domains are considered.