Accuracy and Stability of Numerical Algorithms, Second Edition

Chapter 23: Fast Matrix Multiplication

A simple but extremely valuable bit of equipment in matrix multiplication consists of two plain cards, with a re-entrant right angle cut out of one or both of them if symmetric matrices are to be multiplied. In getting the element of the ith row and jth column of the product, the ith row of the first factor and the jth column of the second should be marked by a card beside, above, or below it.

- HAROLD HOTELLING, Some New Methods in Matrix Calculation (1943)

It was found that multiplication of matrices using punched card storage could be a highly efficient process on the Pilot ACE, due to the relative speeds of the Hollerith card reader used for input (one number per 16 ms.) and the automatic multiplier (2 ms.). While a few rows of one matrix were held in the machine the matrix to be multiplied by it was passed through the card reader. The actual computing and selection of numbers from store occupied most of the time between the passage of successive rows of the cards through the reader, so that the overall time was but little longer than it would have been if the machine had been able to accommodate both matrices.

- MICHAEL WOODGER, The History and Present Use of Digital Computers at the National Physical Laboratory (1958)

23.1 Methods

A fast matrix multiplication method forms the product of two n n matrices in O( n ?) arithmetic operations, where ?

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: ID Card Readers and Encoders
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.