Fundamentals of Algorithms – serie

This brief book on Newton’s method is a user-oriented guide to algorithms and implementation. In just over 100 pages, it shows, via algorithms in pseudocode, in MATLAB, and with several examples, how one can choose an appropriate Newton-type method for a given problem, diagnose problems, and write an efficient solver or apply one written by others. It contains trouble-shooting guides to the major algorithms, their most common failure modes, and the likely causes of failure. It also includes many worked-out examples (available on the SIAM website) in pseudocode and a collection of MATLAB codes, allowing readers to experiment with the algorithms easily and implement them in other languages.The author covers both simple techniques for scalar problems as well as contemporary techniques (e.g. inexact Newton methods and Newton-Krylov techniques) for larger scale problems. This book is intended to complement Kelley’s larger book, Iterative Methods for Linear and Nonlinear Equations (SIAM, 1995), which focuses on in-depth treatment of convergence theory, but does not discuss the details of solving particular problems, implementation in any particular language, or evaluating a solver for a given problem.

Computational scientists often encounter problems requiring the solution of sparse systems of linear equations. Attacking these problems efficiently requires an in-depth knowledge of the underlying theory, algorithms, and data structures found in sparse matrix software libraries. Here, Davis presents the fundamentals of sparse matrix algorithms to provide the requisite background. The book includes CSparse, a concise downloadable sparse matrix package that illustrates the algorithms and theorems presented in the book and equips readers with the tools necessary to understand larger and more complex software packages.With a strong emphasis on MATLAB® and the C programming language, Direct Methods for Sparse Linear Systems equips readers with the working knowledge required to use sparse solver packages and write code to interface applications to those packages. The book also explains how MATLAB performs its sparse matrix computations.

When we use a camera, we want the recorded image to be a faithful representation of the scene that we see, but every image is more or less blurry. In image deblurring, the goal is to recover the original, sharp image by using a mathematical model of the blurring process. The key issue is that some information on the lost details is indeed present in the blurred image, but this “hidden” information can be recovered only if we know the details of the blurring process. Deblurring Images describes the deblurring algorithms and techniques collectively known as spectral filtering methods, in which the singular value decomposition - or a similar decomposition with spectral properties - is used to introduce the necessary regularization or filtering in the reconstructed image. The concise MATLAB® implementations described in the book provide a template of techniques that can be used to restore blurred images from many applications.This book’s treatment of image deblurring is unique in two ways: it includes algorithmic and implementation details; and by keeping the formulations in terms of matrices, vectors, and matrix computations, it makes the material accessible to a wide range of readers. Students and researchers in engineering will gain an understanding of the linear algebra behind filtering methods, while readers in applied mathematics, numerical analysis, and computational science will be exposed to modern techniques to solve realistic large-scale problems in image processing.With a focus on practical and efficient algorithms, Deblurring Images includes many examples, sample image data, and MATLAB codes that allow readers to experiment with the algorithms. It also incorporates introductory material, such as how to manipulate images within the MATLAB environment, making it a stand-alone text. Pointers to the literature are given for techniques not covered in the book.

Toeplitz systems arise in a variety of applications in mathematics, scientific computing, and engineering, including numerical partial and ordinary differential equations, numerical solutions of convolution-type integral equations, stationary autoregressive time series in statistics, minimal realization problems in control theory, system identification problems in signal processing, and image restoration problems in image processing.This practical book introduces current developments in using iterative methods for solving Toeplitz systems based on the preconditioned conjugate gradient method. The authors focus on the important aspects of iterative Toeplitz solvers and give special attention to the construction of efficient circulant preconditioners. Applications of iterative Toeplitz solvers to practical problems are addressed, enabling readers to use the book’s methods and algorithms to solve their own problems.An appendix containing the MATLAB® programs used to generate the numerical results is included.

Whenever images taken at different times, from different viewpoints, and/or by different sensors need to be compared, merged, or integrated, image registration is required. Registration, also known as alignment, fusion, or warping, is the process of transforming data into a common reference frame.This book provides an overview of state-of-the-art registration techniques from theory to practice, plus numerous exercises designed to enhance readers’ understanding of the principles and mechanisms of the described techniques. It also provides, via a supplementary Web page, free access to FAIR.m, a package that is based on the MATLAB® software environment, which enables readers to experiment with the proposed algorithms and explore the presented examples in much more depth.

Inverse problems arise when we reconstruct a sharper image from a blurred one or reconstruct the underground mass density from measurements of the gravity above the ground. When we solve an inverse problem, we compute the source that gives rise to some observed data using a mathematical model for the relation between the source and the data.This book gives an introduction to the practical treatment of inverse problems by means of numerical methods, with a focus on basic mathematical and computational aspects. To solve inverse problems, we demonstrate that insight about them goes hand in hand with algorithms.Discrete Inverse Problems includes a number of tutorial exercises that give the reader hands-on experience with the methods, difficulties, and challenges associated with the treatment of inverse problems. It also includes examples and figures that illustrate the theory and algorithms.

This book describes and analyzes all available alternating projection methods for solving the general problem of finding a point in the intersection of several given sets belonging to a Hilbert space. For each method the authors describe and analyze convergence, speed of convergence, acceleration techniques, stopping criteria, and applications. Different types of algorithms and applications are studied for subspaces, linear varieties, and general convex sets. The authors also unify these algorithms into a common theoretical framework.Alternating Projection Methods is a comprehensive and accessible source of information, providing readers with the theoretical and practical aspects of the most relevant alternating projection methods. It features several acceleration techniques for every method it presents and analyzes, including schemes that cannot be found in other books. It also provides full descriptions of several important mathematical problems and specific applications for which the alternating projection methods represent an efficient option. Examples and problems that illustrate this material are also included.

This concise and comprehensive treatment of the basic theory of algebraic Riccati equations describes the classical as well as the more advanced algorithms for their solution in a manner that is accessible to both practitioners and scholars. It is the first book in which nonsymmetric algebraic Riccati equations are treated in a clear and systematic way. Some proofs of theoretical results have been simplified and a unified notation has been adopted.Readers will find a discussion of doubling algorithms, which are effective in solving algebraic Riccati equations, and a detailed description of all classical and advanced algorithms for solving algebraic Riccati equations, along with their MATLAB® codes. This will help the reader gain understanding of the computational issues and provide ready-to-use implementation of the different solution techniques.

This book focuses on Augmented Lagrangian techniques for solving practical constrained optimization problems. The authors rigorously delineate mathematical convergence theory based on sequential optimality conditions and novel constraint qualifications. They also orient the book to practitioners by giving priority to results that provide insight on the practical behavior of algorithms and by providing geometrical and algorithmic interpretations of every mathematical result, and they fully describe a freely available computational package for constrained optimization and illustrate its usefulness with applications.

Data assimilation is an approach that combines observations and model output, with the objective of improving the latter. This book places data assimilation into the broader context of inverse problems and the theory, methods, and algorithms that are used for their solution. It provides a framework for, and insight into, the inverse problem nature of data assimilation, emphasising 'why' and not just 'how'. Methods and diagnostics are emphasised, enabling readers to readily apply them to their own field of study. This comprehensive guide is accessible to non-experts and contains numerous examples and diverse applications from a broad range of domains, including geophysics, environmental acoustics, medical imaging, mechanical and biomedical engineering, economics and finance, and traffic control and urban planning. Readers will also find included the latest methods for advanced data assimilation, combining variational and statistical approaches.

This book provides an elementary yet comprehensive introduction to the numerical solution of partial differential equations (PDEs). Used to model important phenomena, such as the heating of apartments and the behavior of electromagnetic waves, these equations have applications in engineering and the life sciences, and most can only be solved approximately using computers.Numerical Analysis of Partial Differential Equations Using Maple and MATLAB provides detailed descriptions of the four major classes of discretization methods for PDEs (finite difference method, finite volume method, spectral method, and finite element method) and runnable MATLAB® code for each of the discretization methods and exercises. It also gives self-contained convergence proofs for each method using the tools and techniques required for the general convergence analysis but adapted to the simplest setting to keep the presentation clear and complete.This book is intended for advanced undergraduate and early graduate students in numerical analysis and scientific computing and researchers in related fields. It is appropriate for a course on numerical methods for partial differential equations.

Eigenvalue computations are ubiquitous in science and engineering. John Francis’s implicitly shifted QR algorithm has been the method of choice for small to medium sized eigenvalue problems since its invention in 1959. This book presents a new view of this classical algorithm. While Francis’s original procedure chases bulges, the new version chases core transformations, which allows the development of fast algorithms for eigenvalue problems with a variety of special structures. This also leads to a fast and backward stable algorithm for computing the roots of a polynomial by solving the companion matrix eigenvalue problem. The authors received a SIAM Outstanding Paper prize for this work.This book will be of interest to researchers in numerical linear algebra and their students.

Nonlinear matrix equations arise frequently in applied science and engineering. This is the first book to provide a unified treatment of structure-preserving doubling algorithms, which have been recently studied and proven effective for notoriously challenging problems, such as fluid queue theory and vibration analysis for high-speed trains. The authors present recent developments and results for the theory of doubling algorithms for nonlinear matrix equations associated with regular matrix pencils, and highlight the use of these algorithms in achieving robust solutions for notoriously challenging problems that other methods cannot.Structure-Preserving Doubling Algorithms for Nonlinear Matrix Equations is intended for researchers and computational scientists. Graduate students may also find it of interest.

This thoroughly revised second edition provides an updated treatment of numerical linear algebra techniques for solving problems in data mining and pattern recognition. Adopting an application-oriented approach, the author introduces matrix theory and decompositions, describes how modern matrix methods can be applied in real life scenarios, and provides a set of tools that students can modify for a particular application.Building on material from the first edition, the author discusses basic graph concepts and their matrix counterparts. He introduces the graph Laplacian and properties of its eigenvectors needed in spectral partitioning and describes spectral graph partitioning applied to social networks and text classification. Examples are included to help readers visualize the results. This new edition also presents matrix-based methods that underlie many of the algorithms used for big data.The book provides a solid foundation to further explore related topics and presents applications such as classification of handwritten digits, text mining, text summarization, PageRank computations related to the Google search engine, and facial recognition. Exercises and computer assignments are available on a Web page that supplements the book.Matrix Methods in Data Mining and Pattern Recognition, Second Edition is primarily for undergraduate students who have previously taken an introductory scientific computing/numerical analysis course and graduate students in data mining and pattern recognition areas who need an introduction to linear algebra techniques.

This book addresses an important class of mathematical problems (the Riemann problem) for first-order hyperbolic partial differential equations (PDEs), which arise when modeling wave propagation in applications such as fluid dynamics, traffic flow, acoustics, and elasticity.It covers the fundamental ideas related to classical Riemann solutions, including their special structure and the types of waves that arise, as well as the ideas behind fast approximate solvers for the Riemann problem.The emphasis is on the general ideas, but each chapter delves into a particular application. The book is available in electronic form as a collection of Jupyter notebooks that contain executable computer code and interactive figures and animations.

The location of an object can often be determined from indirect measurements using a process called estimation. This book explains the mathematical formulation of location-estimation problems and the statistical properties of these mathematical models. It also presents algorithms that are used to resolve these models to obtain location estimates, including the simplest linear models, nonlinear models (location estimation using satellite navigation systems and estimation of the signal arrival time from those satellites), dynamical systems (estimation of an entire path taken by a vehicle), and models with integer ambiguities (GPS location estimation that is centimeter-level accurate).Location Estimation from the Ground Up clearly presents analytic and algorithmic topics not covered in other books, including simple algorithms for Kalman filtering and smoothing, the solution of separable nonlinear optimization problems, estimation with integer ambiguities, and the implicit-function approach to estimating covariance matrices when the estimator is a minimizer or maximizer. It takes a unified approach to estimation while highlighting the differences between classes of estimation problems. The only book on estimation written for math and computer science students and graduates, it includes problems at the end of each chapter, many with solutions, to help readers deepen their understanding of the material and guide them through small programming projects that apply theory and algorithms to the solution of real-world location-estimation problems.The book’s core audience consists of engineers, including software engineers and algorithm developers, and graduate students who work on location-estimation projects and who need help translating the theory into algorithms, code, and deep understanding of the problem in front of them. Instructors in mathematics, computer science, and engineering may also find the book of interest as a primary or supplementary text for courses in location estimation and navigation.

In Computed Tomography: Algorithms, Insight, and Just Enough Theory, readers will learn about the fundamental computational methods used for image reconstruction in computed tomography (CT). Unique in its emphasis on the interplay of modeling, computing, and algorithm development, the book presents underlying mathematical models for motivating and deriving the basic principles of CT reconstruction methods, along with insight into their advantages, limitations, and computational aspects.Computed Tomography: Algorithms, Insight, and Just Enough Theory:Develops the mathematical and computational aspects of three main classes of reconstruction methods.Emphasizes the link between CT and numerical methods, which is rarely found in current literature.Describes the effects of incomplete data using both microlocal analysis and the singular value decomposition (SVD).Contains computer exercises using MATLAB that allow readers to experiment with the algorithms and make the book suitable for teaching and self-study.This book is aimed at students, researchers, and practitioners. As a textbook, it is appropriate for the following courses: Advanced Numerical Analysis, Special Topics on Numerical Analysis, Topics on Data Science, Topics on Numerical Optimization, and Topics on Approximation Theory.

Iterative methods use successive approximations to obtain more accurate solutions. Iterative Methods and Preconditioners for Systems of Linear Equationspresents historical background,derives complete convergence estimates for all methods, illustrates and provides Matlab codes for all methods, and studies and tests all preconditioners first as stationary iterative solvers.This textbook is appropriate for undergraduate and graduate students in need of an overview or of deeper knowledge about iterative methods. It can be used in courses on Advanced Numerical Analysis, Special Topics on Numerical Analysis, Topics on Data Science, Topics on Numerical Optimization, and Topics on Approximation Theory. Scientists and engineers interested in new topics and applications will also find the text useful.