This cross-disciplinary volume brings together theoretical mathematicians, engineers and numerical analysts and publishes surveys and research articles related to topics such as fast algorithms, in which the late Georg Heinig made outstanding achievements.

This book provides an extensive introduction to numerical computing from the viewpoint of backward error analysis. The intended audience includes students and researchers in science, engineering and mathematics. The approach taken is somewhat informal owing to the wide variety of backgrounds of the readers, but the central ideas of backward error and sensitivity (conditioning) are systematically emphasized. The book is divided into four parts: Part I provides the background preliminaries including floating-point arithmetic, polynomials and computer evaluation of functions; Part II covers numerical linear algebra; Part III covers interpolation, the FFT and quadrature; and Part IV covers numerical solutions of differential equations including initial-value problems, boundary-value problems, delay differential equations and a brief chapter on partial differential equations. The book contains detailed illustrations, chapter summaries and a variety of exercises as well some Matlab codes provided online as supplementary material. “I really like the focus on backward error analysis and condition. This is novel in a textbook and a practical approach that will bring welcome attention." Lawrence F. Shampine A Graduate Introduction to Numerical Methods and Backward Error Analysis” has been selected by Computing Reviews as a notable book in computing in 2013. Computing Reviews Best of 2013 list consists of book and article nominations from reviewers, CR category editors, the editors-in-chief of journals, and others in the computing community.

"The collection of the contributions to these volumes offers a flavor of the plethora of different approaches to attack structured matrix problems. The reader will find that the theory of structured matrices is positioned to bridge diverse applications in the sciences and engineering, deep mathematical theories, as well as computational and numberical issues. The presentation fully illustrates the fact that the technicques of engineers, mathematicisn, and numerical analysts nicely complement each other, and they all contribute to one unified theory of structured matrices"--Back cover.

The conventional numerical methods when applied to multidimensional problems suffer from the so-called "curse of dimensionality", that cannot be eliminated by using parallel architectures and high performance computing. The novel tensor numerical methods are based on a "smart" rank-structured tensor representation of the multivariate functions and operators discretized on Cartesian grids thus reducing solution of the multidimensional integral-differential equations to 1D calculations. We explain basic tensor formats and algorithms and show how the orthogonal Tucker tensor decomposition originating from chemometrics made a revolution in numerical analysis, relying on rigorous results from approximation theory. Benefits of tensor approach are demonstrated in ab-initio electronic structure calculations. Computation of the 3D convolution integrals for functions with multiple singularities is replaced by a sequence of 1D operations, thus enabling accurate MATLAB calculations on a laptop using 3D uniform tensor grids of the size up to 1015. Fast tensor-based Hartree-Fock solver, incorporating the grid-based low-rank factorization of the two-electron integrals, serves as a prerequisite for economical calculation of the excitation energies of molecules. Tensor approach suggests efficient grid-based numerical treatment of the long-range electrostatic potentials on large 3D finite lattices with defects.The novel range-separated tensor format applies to interaction potentials of multi-particle systems of general type opening the new prospects for tensor methods in scientific computing. This research monograph presenting the modern tensor techniques applied to problems in quantum chemistry may be interesting for a wide audience of students and scientists working in computational chemistry, material science and scientific computing.

The new edition of the popular introductory textbook on numerical approximation methods and mathematical analysis, with a unique emphasis on real-world application An Introduction to Numerical Methods and Analysis helps students gain a solid understanding of a wide range of numerical approximation methods for solving problems of mathematical analysis. Designed for entry-level courses on the subject, this popular textbook maximizes teaching flexibility by first covering basic topics before gradually moving to more advanced material in each chapter and section. Throughout the text, students are provided clear and accessible guidance on a wide range of numerical methods and analysis techniques, including root-finding, numerical integration, interpolation, solution of systems of equations, and many others. This fully revised third edition contains new sections on higher-order difference methods, the bisection and inertia method for computing eigenvalues of a symmetric matrix, a completely re-written section on different methods for Poisson equations, and spectral methods for higher-dimensional problems. New problem sets—ranging in difficulty from simple computations to challenging derivations and proofs—are complemented by computer programming exercises, illustrative examples, and sample code. This acclaimed textbook: Explains how to both construct and evaluate approximations for accuracy and performance Covers both elementary concepts and tools and higher-level methods and solutions Features new and updated material reflecting new trends and applications in the field Contains an introduction to key concepts, a calculus review, an updated primer on computer arithmetic, a brief history of scientific computing, a survey of computer languages and software, and a revised literature review Includes an appendix of proofs of selected theorems and a companion website with additional exercises, application models, and supplemental resources An Introduction to Numerical Methods and Analysis, Third Edition is the perfect textbook for upper-level undergraduate students in mathematics, science, and engineering courses, as well as for courses in the social sciences, medicine, and business with numerical methods and analysis components.

A solutions manual to accompany An Introduction to Numerical Methods and Analysis, Third Edition An Introduction to Numerical Methods and Analysis helps students gain a solid understanding of a wide range of numerical approximation methods for solving problems of mathematical analysis. Designed for entry-level courses on the subject, this popular textbook maximizes teaching flexibility by first covering basic topics before gradually moving to more advanced material in each chapter and section. Throughout the text, students are provided clear and accessible guidance on a wide range of numerical methods and analysis techniques, including root-finding, numerical integration, interpolation, solution of systems of equations, and many others. This fully revised third edition contains new sections on higher-order difference methods, the bisection and inertia method for computing eigenvalues of a symmetric matrix, a completely re-written section on different methods for Poisson equations, and spectral methods for higher-dimensional problems. New problem sets—ranging in difficulty from simple computations to challenging derivations and proofs—are complemented by computer programming exercises, illustrative examples, and sample code. This acclaimed textbook: Explains how to both construct and evaluate approximations for accuracy and performance Covers both elementary concepts and tools and higher-level methods and solutions Features new and updated material reflecting new trends and applications in the field Contains an introduction to key concepts, a calculus review, an updated primer on computer arithmetic, a brief history of scientific computing, a survey of computer languages and software, and a revised literature review Includes an appendix of proofs of selected theorems and author-hosted companion website with additional exercises, application models, and supplemental resources

Matrix algorithms are at the core of scientific computing and are indispensable tools in most applications in engineering. This book offers a comprehensive and up-to-date treatment of modern methods in matrix computation. It uses a unified approach to direct and iterative methods for linear systems, least squares and eigenvalue problems. A thorough analysis of the stability, accuracy, and complexity of the treated methods is given. Numerical Methods in Matrix Computations is suitable for use in courses on scientific computing and applied technical areas at advanced undergraduate and graduate level. A large bibliography is provided, which includes both historical and review papers as well as recent research papers. This makes the book useful also as a reference and guide to further study and research work.

One of the best known fast computational algorithms is the fast Fourier transform method. Its efficiency is based mainly on the special structure of the discrete Fourier transform matrix. Recently, many other algorithms of this type were discovered, and the theory of structured matrices emerged. This volume contains 22 survey and research papers devoted to a variety of theoretical and practical aspects of the design of fast algorithms for structured matrices and related issues. Included are several papers containing various affirmative and negative results in this direction. The theory of rational interpolation is one of the excellent sources providing intuition and methods to design fast algorithms. The volume contains several computational and theoretical papers on the topic. There are several papers on new applications of structured matrices, e.g., to the design of fast decoding algorithms, computing state-space realizations, relations to Lie algebras, unconstrained optimization, solving matrix equations, etc. The book is suitable for mathematicians, engineers, and numerical analysts who design, study, and use fast computational algorithms based on the theory of structured matrices.

The zeros of a polynomial can be readily recovered from its linear factors. The linear factors can be approximated by first splitting a polynomial numerically into the product of its two nonconstant factors and then recursively splitting every computed nonlinear factor in similar fashion. For both the worst and average case inputs the resulting algorithms solve the polynomial factorization and root-finding problems within fixed sufficiently small error bounds by using nearly optimal arithmetic and Boolean time, that is using nearly optimal numbers of arithmetic and bitwise operations; in the case of a polynomial with integer coefficients and simple roots we can immediately extend factorization to root isolation, that is to computing disjoint covering discs, one for every root on the complex plane. The presented algorithms compute highly accurate approximations to all roots nearly as fast as one reads the input coefficients. Furthermore, our algorithms allow processor efficient parallel acceleration, which enables root-finding, factorization, and root isolation in polylogarithmic arithmetic and Boolean time. The chapter thoroughly covers the design and analysis of these algorithms, including auxiliary techniques of independent interest. At the end we compare the presented polynomial root-finders with alternative ones, in particular with the popular algorithms adopted by users based on supporting empirical information. We also comment on some promising directions to further progress.

This book is about computing eigenvalues, eigenvectors, and invariant subspaces of matrices. Treatment includes generalized and structured eigenvalue problems and all vital aspects of eigenvalue computations. A unique feature is the detailed treatment of structured eigenvalue problems, providing insight on accuracy and efficiency gains to be expected from algorithms that take the structure of a matrix into account.