BIZNIQUE / LINEAR ALGEBRA / 07
Understand matrix multiplication cost
Understand matrix multiplication cost
Use dimensions to estimate arithmetic work before reaching for performance claims.
Embedded Files
THE IDEA
Read the example.
Read the example.
The straightforward dense matrix product forms mp dot products, each with n terms. That means mnp multiplications and mp(n−1) additions. Actual time also depends on memory movement, layout, numerical libraries and hardware.
(m × n)(n × p) → m × p
Use it well
Use it well
Operation counts are a useful model, not a stopwatch. Tiny matrices, sparse structure and specialised algorithms can behave differently.
TRY IT YOURSELF
A quick check.
A quick check.
How many multiplications does a 20-by-30 matrix times a 30-by-10 matrix require in the straightforward algorithm?
Check your reasoning
Check your reasoning
20×30×10 = 6,000 multiplications.
Page updated
Google Sites
Report abuse