Software Environments and Tools – serie

Devoted to the assessment of the quality of numerical results produced by computers, this book addresses the question: how does finite precision affect the convergence of numerical methods on the computer when convergence has been proven in exact arithmetic?Finite precision computations are at the heart of the daily activities of many engineers and researchers in all branches of applied mathematics. Written in an informal style, the book combines techniques from engineering and mathematics to describe the rigorous and novel theory of computability in finite precision. In the challenging cases of nonlinear problems, theoretical analysis is supplemented by software tools to explore the stability on the computer.Round-off errors are often considered negatively, as a severe limitation on the purity of exact computations. The authors show how the necessarily finite precision of the computer arithmetic can be turned into an asset when describing physical phenomena.Special Features:Discusses the influence of nonnormality on the reliability of algorithms and methods in relation to physics and technology.Shows rounding errors to be treatable by classical analysis due to the framework of backward error analysis.Presents a unified theory of convergence and stability by means of elementary mathematics.Illustrates how to take advantage of modern programming environments to do experimental investigation of the stability of a problem or of the reliability of an algorithm or a numerical method.Contains, for the first time in a book, a unified survey of normwise/componentwise error analysis for linear algebra (linear systems, least squares, and eigenproblems) and roots of polynomials.

Provides an introduction to computer benchmarking. Hockney includes material concerned with the definition of performance parameters and metrics and defines a set of suitable metrics with which to measure performance and units with which to express them. He also presents new ideas resulting from the application of dimensional analysis to the field of computer benchmarking. This results in the definition of a dimensionless universal scaling diagram that completely describes the scaling properties of a class of computer benchmarks on a single diagram, for all problem sizes and all computers describable by a defined set of hardware parameters.The principle of computational similarity, which states the requirements for two computer programs to have the same optimum self-speedup, optimum number of processors, and scaling, is also described.

This volume conveniently brings together updated versions of 30 articles that originally appeared in SIAM News from 1990 to 1995. The objective of the column from which the articles are taken is to present applications that have been successfully treated on advanced architecture computers. Astfalk edits this popular series of articles in SIAM's flagship publication, SIAM News. Algorithmic issues addressed are those which have found general use in building parallel codes for solving problems. In addition to updates that reflect advances and changes in the field of applications on advanced architecture computers, Astfalk has added an index and introductory comments to each article, making this book cohesive and interesting to practitioners and researchers alike.Although some of the computers used in older articles are no longer available and some of the languages are rarely used, what is valuable in these articles is the diversity of areas to which advanced computing can be applied. Perhaps more valuable than the diversity are the successful methods used to achieve parallelism. This may be used by others for similar applications. The applications and technology discussed cover many disciplines, with significant overlap. Articles deal with molecular dynamics, optimization/math programming, finance/economics, geometry, and partial differential equations.

ScaLAPACK is an acronym for Scalable Linear Algebra Package or Scalable LAPACK. It is a library of high-performance linear algebra routines for distributed memory message-passing MIMD computers and networks of workstations supporting parallel virtual machine (PVM) and/or message passing interface (MPI). It is a continuation of the LAPACK project, which designed and produced analogous software for workstations, vector supercomputers, and shared memory parallel computers. Both libraries contain routines for solving systems of linear equations, least squares problems, and eigenvalue problems. The goals of both projects are efficiency, scalability, reliability, portability, flexibility, and ease of use.ScaLAPACK includes routines for the solution of dense, band, and tridiagonal linear systems of equations, condition estimation and iterative refinement, for LU and Cholesky factorization, matrix inversion, full-rank linear least squares problems, orthogonal and generalized orthogonal factorizations, orthogonal transformation routines, reductions to upper Hessenberg, bidiagonal and tridiagonal form, reduction of a symmetric-definite/ Hermitian-definite generalized eigenproblem to standard form, the symmetric/Hermitian, generalized symmetric/Hermitian, and nonsymmetric eigenproblem, and the singular value decomposition. Prototype codes are provided for out-of-core linear solvers for LU, Cholesky, and QR, the matrix sign function for eigenproblems, an HPF interface to a subset of ScaLAPACK routines, and SuperLU.Software is available in single-precision real, double-precision real, single-precision complex, and double-precision complex. The software has been written to be portable across a wide range of distributed-memory environments such as the Cray T3, IBM SP, Intel series, TM CM-5, networks of workstations, and any system for which PVM or MPI is available.Each Users' Guide includes a CD-ROM containing the HTML version of the ScaLAPACK Users' Guide, the source code for ScaLAPACK and LAPACK, testing and timing programs, prebuilt versions of the library for a number of computers, example programs, and the full set of LAPACK Working Notes.

A guide to understanding and using the software package ARPACK to solve large algebraic eigenvalue problems. The software described is based on the implicitly restarted Arnoldi method, which has been heralded as one of the three most important advances in large scale eigenanalysis in the past ten years. The book explains the acquisition, installation, capabilities, and detailed use of the software for computing a desired subset of the eigenvalues and eigenvectors of large (sparse) standard or generalized eigenproblems. It also discusses the underlying theory and algorithmic background at a level that is accessible to the general practitioner.Other important topics covered include:Treatment of the non-Hermitian problem.Explanation of the theory behind Krylov subspace projection methods, implicit restarting, and spectral transformation.Explanation of the implicitly restarted Arnoldi method (IRAM).Descriptions of the various templates (driver routines) to interface an application with ARPACK to solve a wide variety of problems.ARPACK is a collection of Fortran 77 subroutines designed to solve large-scale eigenvalue problems. It provides state-of-the-art software for solving large (sparse) Hermitian, non-Hermitian, standard, or generalized eigenvalue problems from significant application areas. It is one of the few software packages to successfully address the non-Hermitian problem. Practitioners will be able to better understand the full capabilities of ARPACK (ARnoldi PACKage) and grasp the underlying theory more thoroughly with this book.

Intended mainly for use as a reference manual, this third edition encompasses all the improvements of the newest version of the PLTMG software package, including the following:The data structures defining the domain (triangulation and skeleton) have been simplified; more general boundary conditions are allowed.The internal data structure (triangle tree) has been replaced by a simple triangulation; the adaptive algorithms have been revised to use this simple data structure.The linear equations solvers are multigraph methods, which are simple ILU factorizations with strong connections to the hierarchical basis multigrid method.The graphics packages have been improved and now include expanded options.The test driver has a new X-Windows gui option.

Presents a unified treatment of recently developed techniques and current understanding about solving systems of linear equations and large scale eigenvalue problems on high-performance computers, and provides a rapid introduction to the world of vector and parallel processing for these linear algebra applications.Topics include major elements of advanced-architecture computers and their performance, recent algorithmic development, and software for direct solution of dense matrix problems, direct solution of sparse systems of equations, iterative solution of sparse systems of equations, and solution of large sparse eigenvalue problems.This book supersedes the SIAM publication Solving Linear Systems on Vector and Shared Memory Computers, which appeared in 1990. The new book includes a considerable amount of new material in addition to incorporating a substantial revision of existing text.

LAPACK is a library of numerical linear algebra subroutines designed for high performance on workstations, vector computers, and shared memory multiprocessors. Release 3.0 of LAPACK introduces new routines and extends the functionality of existing routines. The most significant new routines and functions include: a faster singular value decomposition computed by divide-and-conquer; faster routines for solving rank-deficient least squares problems: using QR with column pivoting; using the SVD based on divide-and-conquer; new routines for the generalized symmetric eigenproblem: faster routines based on divide-and-conquer; routines based on bisection/inverse iteration, for computing part of the spectrum; faster routine for the symmetric eigen problem using “relatively robust eigenvector algorithm”; new simple and expert drivers for the generalized nonsymmetric eigenproblem, including error bounds; solver for generalized Sylvester equation, used in computational routines Each Users' Guide comes with a "Quick Reference Guide" card.

This is the only book on spectral methods built around MATLAB programs. Along with finite differences and finite elements, spectral methods are one of the three main technologies for solving partial differential equations on computers. Since spectral methods involve significant linear algebra and graphics they are very suitable for the high level programming of MATLAB. This hands-on introduction is built around forty short and powerful MATLAB programs, which the reader can download from the World Wide Web. This book presents the key ideas along with many figures, examples, and short, elegant MATLAB programs for readers to adapt to their own needs. It covers ODE and PDE boundary value problems, eigenvalues and pseudospectra, linear and nonlinear waves, and numerical quadrature.

Large-scale problems of engineering and scientific computing often require solutions of eigenvalue and related problems. This book gives a unified overview of theory, algorithms, and practical software for eigenvalue problems. It organizes this large body of material to make it accessible for the first time to the many nonexpert users who need to choose the best state-of-the-art algorithms and software for their problems. Using an informal decision tree, just enough theory is introduced to identify the relevant mathematical structure that determines the best algorithm for each problem.The algorithms and software at the ""leaves"" of the decision tree range from the classical QR algorithm, which is most suitable for small dense matrices, to iterative algorithms for very large generalized eigenvalue problems. Algorithms are presented in a unified style as templates, with different levels of detail suitable for readers ranging from beginning students to experts. The authors' comprehensive treatment includes a treasure of further bibliographic information.

Offers a comprehensive, tutorial-style, hands-on, introductory and intermediate-level treatment of all the essential ingredients for achieving high performance in numerical computations on modern computers. The authors explain computer architectures, data traffic, and issues related to performance of serial and parallel code optimization exemplified by actual programs written for algorithms of wide interest. The unique hands-on style is achieved by extensive case studies using realistic computational problems. The performance gain obtained by applying the techniques described in this book can be very significant.The book bridges the gap between the literature in system architecture, the one in numerical methods and the occasional descriptions of optimization topics in computer vendors' literature. It also allows readers to better judge the suitability of certain computer architecture to their computational requirements. In contrast to standard textbooks on computer architecture and on programming techniques the book treats these topics together at the level necessary for writing high-performance programs. The book facilitates easy access to these topics for computational scientists and engineers mainly interested in practical issues related to efficient code development.

LAPACK95 is a Fortran 95 interface to the Fortran 77 LAPACK library. It is relevant for anyone who writes in the Fortran 95 language and needs reliable software for basic numerical linear algebra. It improves upon the original user-interface to the LAPACK package, taking advantage of the considerable simplifications that Fortran 95 allows. LAPACK95 Users’ Guide provides an introduction to the design of the LAPACK95 package, a detailed description of its contents, reference manuals for the leading comments of the routines, and example programs.

Provides sophisticated numerical methods for the fast and accurate solution of a variety of equations, including ordinary differential equations, delay equations, integral equations, functional equations, and some partial differential equations, as well as boundary value problems. It introduces many modeling techniques and methods for analyzing the resulting equations.Instructors, students, and researchers will all benefit from this book, which demonstrates how to use software tools to simulate and study sets of equations that arise in a variety of applications. Instructors will learn how to use computer software in their differential equations and modeling classes, while students will learn how to create animations of their equations that can be displayed on the World Wide Web. Researchers will be introduced to useful tricks that will allow them to take full advantage of XPPAUT’s capabilities. In addition, readers will learn several concepts from the field of dynamical systems, including chaos theory, how systems depend on parameters, and how simple physical systems can lead to complicated behavior.XPPAUT is a tool for simulating, animating, and analyzing dynamical systems that evolved from tools developed by the author for studying nonlinear oscillations. XPPAUT offers several advantages over MATLAB, Maple, and Mathematica, including the following: 1) A faster way to numerically solve differential equations and do numerical integration.2) More flexibility with integration, including interactive integration that allows the user to see the progress of the solution as it is computed. 3) An interface with AUTO, a continuation packae.4) Simpler syntax for setting up differentiation equations. 5) Free downloading of the source code.

This book is divided into two distinct parts. The first part reviews the evolution of one of the most widely used numerical techniques in the industry. The development of the method, as it became more robust, is demonstrated through easy-to-understand algorithms. The second part contains industrial applications drawn from the author’s experience. These chapters provide a unique interaction between the numerical algorithms and their engineering applications.

The second edition of Understanding Search Engines follows the basic premise of the first edition by discussing many of the key design issues for building search engines and emphasizing the important role that applied mathematics can play in improving information retrieval. The authors discuss important data structures, algorithms, and software as well as user-centered issues such as interfaces, manual indexing, and document preparation. Readers will find that the second edition includes significant changes that bring the text up to date on current information retrieval methods. For example, the authors have added a completely new chapter on link-structure algorithms used in search engines such as Google, and the chapter on user interface has been rewritten to specifically focus on search engine usability. To reflect updates in the literature on information retrieval, the authors have added new recommendations for further reading and expanded the bibliography. In addition, the index has been updated and streamlined to make it more reader friendly.

Numerical software is used to test scientific theories, design airplanes and bridges, operate manufacturing lines, control power plants and refineries, analyze financial derivatives, identify genomes, and provide the understanding necessary to derive and analyze cancer treatments. Because of the high stakes involved, it is essential that results computed using software be accurate, reliable, and robust. Unfortunately, developing accurate and reliable scientific software is notoriously difficult. This book investigates some of the difficulties related to scientific computing and provides insight into how to overcome them and obtain dependable results. The tools to assess existing scientific applications are described, and a variety of techniques that can improve the accuracy and reliability of newly developed applications is discussed.Accuracy and Reliability in Scientific Computing can be considered a handbook for improving the quality of scientific computing. It will help computer scientists address the problems that affect software in general as well as the particular challenges of numerical computation: approximations occurring at all levels, continuous functions replaced by discretized versions, infinite processes replaced by finite ones, and real numbers replaced by finite precision numbers. Divided into three parts, it starts by illustrating some of the difficulties in producing robust and reliable scientific software. Well-known cases of failure are reviewed and the what and why of numerical computations are considered. The second section describes diagnostic tools that can be used to assess the accuracy and reliability of existing scientific applications. In the last section, the authors describe a variety of techniques that can be employed to improve the accuracy and reliability of newly developed scientific applications. The authors of the individual chapters are international experts, many of them members of the IFIP Working Group on Numerical Software.The book contains condensed information on the main features of six major programming languages — Ada, C, C++, Fortran, Java, and Python — and the INTLAB toolbox of the MATLAB? software and the PRECISE toolbox of Fortran are discussed in detail. This book has an accompanying website, with codes, links, color versions of some illustrations, and additional material.

Scientific computing has often been called the third approach to scientific discovery, emerging as a peer to experimentation and theory. Historically, the synergy between experimentation and theory has been well understood: experiments give insight into possible theories, theories inspire experiments, experiments reinforce or invalidate theories, and so on. As scientific computing has evolved to produce results that meet or exceed the quality of experimental and theoretical results, it has become indispensable.Parallel processing has been an enabling technology in scientific computing for more than 20 years. This book is the first in-depth discussion of parallel computing in 10 years; it reflects the mix of topics that mathematicians, computer scientists, and computational scientists focus on to make parallel processing effective for scientific problems. Presently, the impact of parallel processing on scientific computing varies greatly across disciplines, but it plays a vital role in most problem domains and is absolutely essential in many of them. Parallel Processing for Scientific Computing is divided into four parts: The first concerns performance modeling, analysis, and optimization; the second focuses on parallel algorithms and software for an array of problems common to many modeling and simulation applications; the third emphasizes tools and environments that can ease and enhance the process of application development; and the fourth provides a sampling of applications that require parallel computing for scaling to solve larger and realistic models that can advance science and engineering.

This is the first book on parallel MATLAB and the first parallel computing book focused on the design, code, debug, and test techniques required to quickly produce well-performing parallel programs.MATLAB is currently the dominant language of technical computing with one million users worldwide, many of whom can benefit from the increased power offered by inexpensive multicore and multinode parallel computers. MATLAB is an ideal environment for learning about parallel computing, allowing the user to focus on parallel algorithms instead of the details of implementation.Parallel MATLAB for Multicore and Multinode Computers covers more parallel algorithms and parallel programming models than any other parallel programming book due to the succinctness of MATLAB. It presents a hands-on approach with numerous example programs; wherever possible, the examples are drawn from widely known and well-documented parallel benchmark codes that are representative of many real applications across the field of technical computing.

Graphs are among the most important abstract data types in computer science, and the algorithms that operate on them are critical to modern life. Graphs have been shown to be powerful tools for modeling complex problems because of their simplicity and generality. Graph algorithms are one of the pillars of mathematics, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Algorithms on graphs are applied in many ways in today’s world – from Web rankings to metabolic networks, from finite element meshes to semantic graphs. The current exponential growth in graph data has forced a shift to parallel computing for executing graph algorithms. Implementing parallel graph algorithms and achieving good parallel performance have proven difficult. This book addresses these challenges by exploiting the well-known duality between a canonical representation of graphs as abstract collections of vertices and edges and a sparse adjacency matrix representation. This linear algebraic approach is widely accessible to scientists and engineers who may not be formally trained in computer science. The authors show how to leverage existing parallel matrix computation techniques and the large amount of software infrastructure that exists for these computations to implement efficient and scalable parallel graph algorithms. The benefits of this approach are reduced algorithmic complexity, ease of implementation, and improved performance. Graph Algorithms in the Language of Linear Algebra is the first book to cover graph algorithms accessible to engineers and scientists not trained in computer science but having a strong linear algebra background, enabling them to quickly understand and apply graph algorithms. It also covers array-based graph algorithms, showing readers how to express canonical graph algorithms using a highly elegant and efficient array notation and how to tap into the large range of tools and techniques that have been built for matrices and tensors; parallel array-based algorithms, demonstrating with examples how to easily implement parallel graph algorithms using array-based approaches, which enables readers to address much larger graph problems; and array-based theory for analyzing graphs, providing a template for using array-based constructs to develop new theoretical approaches for graph analysis.

Implicit filtering is a way to solve bound-constrained optimization problems for which derivative information is not available. Unlike methods that use interpolation to reconstruct the function and its higher derivatives, implicit filtering builds upon coordinate search and then interpolates to get an approximation of the gradient.The author describes the algorithm, its convergence theory, and a new MATLAB® implementation, and includes three case studies. This book is unique in that it is the only one in the area of derivative-free or sampling methods and is accompanied by publicly available software. It is also designed as a software manual and as a reference for implicit filtering — one can approach the book as a consumer of the software, as a student, or as a researcher in sampling and derivative-free methods. The book includes a chapter on convergence theory that is both accessible to students and an overview of recent results on optimization of noisy functions, including results that depend on non-smooth analysis and results on the handling of constraints.Implicit filtering is used in applications in electrical, civil, and mechanical engineering.

This is the first entry-level book on algorithmic (also known as automatic) differentiation (AD), providing fundamental rules for the generation of first- and higher-order tangent-linear and adjoint code. The author covers the mathematical underpinnings as well as applications to real-world numerical simulation programs. Readers will find: Many examples and exercises, including hints to solutions The prototype AD tools dco and dcc for use with the examples and exercises First- and higher-order tangent-linear and adjoint modes for a limited subset of C/C++, provided by the derivative code compiler dcc A supplementary website containing sources of all software discussed in the book, additional exercises and comments on their solutions (growing over the coming years), links to other sites on AD, and errata. Ideal for undergraduate and graduate students, the book is also suitable for researchers and developers at all levels who need an introduction to AD.

This book is a guide to concepts and practice in numerical algebraic geometry - the solution of systems of polynomial equations by numerical methods. Through numerous examples, the authors show how to apply the well-received and widely used open-source Bertini software package to compute solutions, including a detailed manual on syntax and usage options. The authors also maintain a complementary web page where readers can find supplementary materials and Bertini input files.Numerically Solving Polynomial Systems with Bertini approaches numerical algebraic geometry from a user's point of view with numerous examples of how Bertini is applicable to polynomial systems. It treats the fundamental task of solving a given polynomial system and describes the latest advances in the field, including algorithms for intersecting and projecting algebraic sets, methods for treating singular sets, the nascent field of real numerical algebraic geometry, and applications to large polynomial systems arising from differential equations.Those who wish to solve polynomial systems can start gently by finding isolated solutions to small systems, advance rapidly to using algorithms for finding positive-dimensional solution sets (curves, surfaces, etc.), and learn how to use parallel computers on large problems. These techniques are of interest to engineers and scientists in fields where polynomial equations arise, including robotics, control theory, economics, physics, numerical PDEs, and computational chemistry.

Techniques for generating orthogonal polynomials numerically have appeared only recently, within the last 30 or so years. Orthogonal Polynomials in MATLAB describes these techniques and related applications, all supported by MATLAB programs, and presents them in a unique format of exercises and solutions designed by the author to stimulate participation. Important computational problems in the physical sciences are included as models for readers to solve their own problems.