𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A practical algorithm for faster matrix multiplication

✍ Scribed by Igor Kaporin

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
69 KB
Volume
6
Category
Article
ISSN
1070-5325

No coin nor oath required. For personal study only.

✦ Synopsis

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one-or two-level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers.

πŸ“œ SIMILAR VOLUMES

SUMMA: scalable universal matrix multipl
SUMMA: scalable universal matrix multiplication algorithm
✍ Van De Geijn, R. A.; Watts, J. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 341 KB

In the paper we give a straightforward, highly efficient, scalable implementation of common matrix multiplication operations. The algorithms are much simpler than previously published methods, yield better performance, and require less work space. MPI implementations are given, as are performance re

A submatrix algorithm for the matrix-vec
A submatrix algorithm for the matrix-vector multiplication of very large matrices
✍ Roland Lindh; Per-Γ…rke Malmquist πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 179 KB

In self-consistent field (SCF) calculations the construction of the Fock matrix is most time-consuming step. The Fock matrix construction may formally be seen as a matrix-vector multiplication, where the matrix is the supermatrix, Tikl, and the vector is the first-order density matrix, yi. This form

A new parallel matrix multiplication alg
A new parallel matrix multiplication algorithm on distributed-memory concurrent computers
✍ Choi, Jaeyoung πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 139 KB πŸ‘ 3 views

We present a new fast and scalable matrix multiplication algorithm called DIMMA (distribution-independent matrix multiplication algorithm) for block cyclic data distribution on distributed-memory concurrent computers. The algorithm is based on two new ideas; it uses a modified pipelined communicatio

Recursive T-matrix algorithm for multipl
Recursive T-matrix algorithm for multiple metallic cylinders
✍ Adnan Şahin; Eric L. Miller πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 205 KB

We present a new application of the recursi¨e T-matrix algorithm to calculate the scattered field from a single or multiple metallic cylinders of arbitrary shapes. Using the equi¨alence theorem, each metallic object is replaced with small metallic cylinders along its perimeter; then scattered fields

A Faster Algorithm for the Inverse Spann
A Faster Algorithm for the Inverse Spanning Tree Problem
✍ Ravindra K. Ahuja; James B. Orlin πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 149 KB

In this paper, we consider the inverse spanning tree problem. Given an undi-0 Ε½ 0 0 . rected graph G s N , A with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0 , the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T 0 is a minimum spanning tre