Fundamentals of Algorithms - Böcker

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.

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.

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.

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.