Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide

A guide to the numerical solution of eigenvalue problems. This book attempts to present the many available methods in an organized fashion, to make it easier for reader to identify the most promising methods.

**Tag(s):**
Linear Algebra

**Publication date**: 01 Nov 2000

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
n/a

**Views**: 15,462

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 01 Aug 2007 08:00:00

Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide

A guide to the numerical solution of eigenvalue problems. This book attempts to present the many available methods in an organized fashion, to make it easier for reader to identify the most promising methods.

Excerpts from the Introduction:

In many large scale scientific or engineering computations, ranging from computing the frequency response of a circuit to the earthquake response of a building to the energy levels of a molecule, one needs to find eigenvalues and eigenvectors of a matrix. There are many mathematical ways to formulate eigenvalue problems, and even more ways have been proposed to solve them numerically. This book is intended to be a guide to finding the best numerical method for an eigenvalue problem.

The current state of the art is such that excellent methods exist for many eigenproblems, especially for small- to medium-sized dense matrices. These algorithms have been made available in programming environments like MATLAB, libraries like LAPACK, and many other commercial and public packages. But for very large and (typically) sparse eigenvalue problems no single best method exists. The sheer number of methods and the complicated ways they depend on mathematical properties of the matrix and trade off efficiency and accuracy make it difficult for experts, let alone general users, to find the best method for a given problem. Good online search facilities and software repositories exist, notably GAMS (Guide to Available Mathematical Software) and NETLIB. These facilities permit searches based on library names, subroutines names, key words, and a taxonomy of topics in numerical computing. But they will not give advice as to which method is best to use for a particular problem. As a result, the authors of this book and other experts are frequently asked for advice in choosing an algorithm. This situation has motivated us to distill our knowledge into this book to make it as widely available as possible.

Here is how we have structured the book. First, we have developed a decision tree to guide the user to the best method. Each node in the tree poses questions about the problem regarding its mathematical structure, the quantities to be computed, and the cost of applying certain operations to the matrix. Second, at the leaves of the decision tree we present templates of recommended algorithms, as well as pointers to available software. A template is a high-level description of an algorithm, suitable for understanding how it works, what parameters the user can tune to control efficiency and accuracy, and how to interpret the output. We discuss this structure in more detail below.

The original model for this book was Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. This earlier book (which has some authors in common with this one) provided a decision tree and templates for iterative methods for the simpler problem of solving a linear system. Eigenvalue problems are inherently more difficult than linear systems, and this means that our level of understanding varies significantly, depending on the eigenvalue problem at hand. Furthermore, the algorithms are much more complicated. So in contrast to this earlier Templates book, we have not attempted to provide complete implementations of each template in a common style and in common programming languages. Instead, we provide a high-level template of each algorithm and point to good public domain implementations in whatever language they are available. All these implementations may be accessed through a Web site we call ETHOME in the text, which refers to http://www.netlib.org/etemplates/ . This Web site will be updated as new and better algorithms become available.

The variety of eigenproblems covered in this book is very wide. Some algorithms are well known and have been thoroughly investigated, whereas other areas are still subject to intensive research. This has led to differences in the style of presentation. Well-understood areas with good "black box" solutions have been kept brief and are written primarily for nonexpert readers, whereas at the other extreme there are contributions that review current research.

In many large scale scientific or engineering computations, ranging from computing the frequency response of a circuit to the earthquake response of a building to the energy levels of a molecule, one needs to find eigenvalues and eigenvectors of a matrix. There are many mathematical ways to formulate eigenvalue problems, and even more ways have been proposed to solve them numerically. This book is intended to be a guide to finding the best numerical method for an eigenvalue problem.

The current state of the art is such that excellent methods exist for many eigenproblems, especially for small- to medium-sized dense matrices. These algorithms have been made available in programming environments like MATLAB, libraries like LAPACK, and many other commercial and public packages. But for very large and (typically) sparse eigenvalue problems no single best method exists. The sheer number of methods and the complicated ways they depend on mathematical properties of the matrix and trade off efficiency and accuracy make it difficult for experts, let alone general users, to find the best method for a given problem. Good online search facilities and software repositories exist, notably GAMS (Guide to Available Mathematical Software) and NETLIB. These facilities permit searches based on library names, subroutines names, key words, and a taxonomy of topics in numerical computing. But they will not give advice as to which method is best to use for a particular problem. As a result, the authors of this book and other experts are frequently asked for advice in choosing an algorithm. This situation has motivated us to distill our knowledge into this book to make it as widely available as possible.

Here is how we have structured the book. First, we have developed a decision tree to guide the user to the best method. Each node in the tree poses questions about the problem regarding its mathematical structure, the quantities to be computed, and the cost of applying certain operations to the matrix. Second, at the leaves of the decision tree we present templates of recommended algorithms, as well as pointers to available software. A template is a high-level description of an algorithm, suitable for understanding how it works, what parameters the user can tune to control efficiency and accuracy, and how to interpret the output. We discuss this structure in more detail below.

The original model for this book was Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. This earlier book (which has some authors in common with this one) provided a decision tree and templates for iterative methods for the simpler problem of solving a linear system. Eigenvalue problems are inherently more difficult than linear systems, and this means that our level of understanding varies significantly, depending on the eigenvalue problem at hand. Furthermore, the algorithms are much more complicated. So in contrast to this earlier Templates book, we have not attempted to provide complete implementations of each template in a common style and in common programming languages. Instead, we provide a high-level template of each algorithm and point to good public domain implementations in whatever language they are available. All these implementations may be accessed through a Web site we call ETHOME in the text, which refers to http://www.netlib.org/etemplates/ . This Web site will be updated as new and better algorithms become available.

The variety of eigenproblems covered in this book is very wide. Some algorithms are well known and have been thoroughly investigated, whereas other areas are still subject to intensive research. This has led to differences in the style of presentation. Well-understood areas with good "black box" solutions have been kept brief and are written primarily for nonexpert readers, whereas at the other extreme there are contributions that review current research.

Tweet

About The Author(s)

No information is available for this author.

No information is available for this author.

No information is available for this author.

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors