Search ACM DL

Search Issue

enter search term and/or author name

**Accumulating Householder transformations, revisited**

Thierry Joffrain, Tze Meng Low, Enrique S. Quintana-Ortí, Robert van de Geijn, Field G. Van Zee

Pages: 169-179

DOI: 10.1145/1141885.1141886

A theorem related to the accumulation of Householder transformations into a single orthogonal transformation known as the compact WY transform is presented. It provides a simple characterization of the computation of this transformation and suggests...

**Improving the performance of reduction to Hessenberg form**

Gregorio Quintana-Ortí, Robert van de Geijn

Pages: 180-194

DOI: 10.1145/1141885.1141887

In this article, a modification of the blocked algorithm for reduction to Hessenberg form is presented that improves performance by shifting more computation from less efficient matrix-vector operations to highly efficient matrix-matrix operations....

**An efficient overloaded implementation of forward mode automatic differentiation in MATLAB**

Shaun A. Forth

Pages: 195-222

DOI: 10.1145/1141885.1141888

The Mad package described here facilitates the evaluation of first derivatives of multidimensional functions that are defined by computer codes written in MATLAB. The underlying algorithm is the well-known forward mode of automatic differentiation...

**Optimizing FIAT with level 3 BLAS**

Robert C. Kirby

Pages: 223-235

DOI: 10.1145/1141885.1141889

Our previous work on FIAT (Finite Element Automatic Tabulator) developed a “computational representation theory ” that allowed us to construct arbitrary order instances of a wide range of finite elements, many of which are infrequently...

**Computing machine-efficient polynomial approximations**

Nicolas Brisebarre, Jean-Michel Muller, Arnaud Tisserand

Pages: 236-256

DOI: 10.1145/1141885.1141890

Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly...

**Sequential reservoir sampling with a nonuniform distribution**

M. Kolonko, D. Wäsch

Pages: 257-273

DOI: 10.1145/1141885.1141891

We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of...

**A Matlab package for automatically generating Runge-Kutta trees, order conditions, and truncation error coefficients**

Frank Cameron

Pages: 274-298

DOI: 10.1145/1141885.1141892

In designing parts of Runge-Kutta methods, order conditions and truncation error coefficients (TECs) are needed. Order conditions and TECs are typically presented as a set of trees combined with rules for producing algebraic expressions from the...

**FILIB++, a fast interval library supporting containment computations**

Michael Lerch, German Tischler, Jürgen Wolff Von Gudenberg, Werner Hofschuster, Walter Krämer

Pages: 299-324

DOI: 10.1145/1141885.1141893

filib++ is an extension of the interval library filib originally developed at the University of Karlsruhe. The most important aim of filib is the fast computation of guaranteed bounds for interval versions of a comprehensive set of...

**Error bounds from extra-precise iterative refinement**

James Demmel, Yozo Hida, William Kahan, Xiaoye S. Li, Sonil Mukherjee, E. Jason Riedy

Pages: 325-351

DOI: 10.1145/1141885.1141894

We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to...

**Algorithm 854**: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II

Peter Benner, Daniel Kressner

Pages: 352-373

DOI: 10.1145/1141885.1141895

This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal symplectic decompositions, implying numerical backward...