Does Divide & Conquer Matrix Multiplication perform the same amount of additions/subtractions as the Classical Matrix multiplication?

Question

Does Divide & Conquer Matrix Multiplication perform the same amount of additions/subtractions as the Classical Matrix multiplication?

I know that they do specifically for Multiplications as they both share the same O(n^3) complexity...

but when I try to count them in the program i'm making, the additions/subtracts are coming to a different numbers, and I'm not sure if this is correct.

If anyone knows for sure please let me know, thanks.

Answer 1

Let's assume square matrices.

If you count the number of additions (there are no subtractions) in classic matrix multiplication, you get N^3 additions. There are N^2 elements, and each element is the dot-product of a row and column consisting of N-1 additions, so almost exactly N^3 additions.

To count the number of additions in divide-and-conquer matrix multiplication, let's see how it works:

Split up NxN matrix into four (N/2)x(N/2) matrices, then treat it as a 2x2 matrix and perform block multiplication recursively. For example multiplying two 8x8 matrices:

┌┌A A A A┐┌B B B B┐┐ ┌┌a a a a┐┌b b b b┐┐
││A A A A││B B B B││ ││a a a a││b b b b││
││A A A A││B B B B││ ││a a a a││b b b b││
│└A A A A┘└B B B B┘│ │└a a a a┘└b b b b┘│
│┌C C C C┐┌D D D D┐│*│┌c c c c┐┌d d d d┐│
││C C C C││D D D D││ ││c c c c││d d d d││
││C C C C││D D D D││ ││c c c c││d d d d││
└└C C C C┘└D D D D┘┘ └└c c c c┘└d d d d┘┘

The new matrix will be:

┌┌       ┐┌       ┐┐
││ Aa+Bc ││ Ab+Bd ││
││       ││       ││
│└       ┘└       ┘│
│┌       ┐┌       ┐│
││ Ca+Dc ││ Cb+Dd ││
││       ││       ││
└└       ┘└       ┘┘
(where for example Aa is a 4x4 matrix multiplication)

Each multiplication of [N/2xN/2]*[N/2xN/2] is a subproblem of size N/2. We must do 8 of these subproblems. This gives us a recurrence from the above:

additions[N] = 8*additions[N/2] + N^2

That is, if we pay the price of N^2 additions, we are allowed to break down the problem of size N into 8 subproblems of size N/2. We can solve using the Master Theorem (or more general Akra-Bazzi Theorem), or by inspection:

additions[N] = 8*(8*(8*(8*(..1..) +(N/8)^2) +(N/4)^2) +(N/2)^2) +N^2

Using the Master Theorem, additions[N] = O(N^(log_2(8))) = O(N^3)

Why would we do this since it's the same order of growth? We wouldn't. It turns out that in order to get better asymptotic complexity, you don't want to do this, you want to use an algebraic trick called Strassen's method. See http://www.cs.berkeley.edu/~jordan/courses/170-fall05/notes/dc.pdf on page 4. Our new recurrence relation comes from counting the number of multiplications and additions as shown on that page. There are 18 additions of [N/2xN/2] matrices required to form an NxN matrix.

additions[N] = 7*additions[N/2] + 18*(N/2)^2
             = 7*additions[N/2] + (18/4)*(N/2)^2

As we see, we have to do one fewer subproblem, but at the cost of doing more work in combining. The master theorem says that additions[N] = O(N^(log_2(7))) ~= O(N^2.807).

So asymptotically, there will be FEWER additions, but only asymptotically. The real story is revealed when we simulate both recurrence relations:

#!/usr/bin/python3

n = 1  # NxN matrix

normal = 1
naive = 1
strassen = 1

print('NUMBER OF ADDITIONS')
print('       NxN |   normal     naive  strassen | best')
print('-'*60)
while n < 1000000000:
    n *= 2

    normal = (n-1)*n**2
    naive = 8*naive + n**2
    strassen = 7*strassen + (18/4)*n**2

    print('{:>10} | {:>8.2e}  {:>8.2e}  {:>8.2e} | {}'.format(
        n,
        normal, naive, strassen/normal,
        'strassen' if strassen<n**3 else 'normal'
    ))

Results:

NUMBER OF ADDITIONS
       NxN |   normal     naive  strassen | best
------------------------------------------------------------
         2 | 4.00e+00  1.20e+01  2.50e+01 | normal
         4 | 4.80e+01  1.12e+02  2.47e+02 | normal
         8 | 4.48e+02  9.60e+02  2.02e+03 | normal
        16 | 3.84e+03  7.94e+03  1.53e+04 | normal
        32 | 3.17e+04  6.45e+04  1.12e+05 | normal
        64 | 2.58e+05  5.20e+05  7.99e+05 | normal
       128 | 2.08e+06  4.18e+06  5.67e+06 | normal
       256 | 1.67e+07  3.35e+07  4.00e+07 | normal
       512 | 1.34e+08  2.68e+08  2.81e+08 | normal
      1024 | 1.07e+09  2.15e+09  1.97e+09 | normal
      2048 | 8.59e+09  1.72e+10  1.38e+10 | normal
      4096 | 6.87e+10  1.37e+11  9.68e+10 | normal
      8192 | 5.50e+11  1.10e+12  6.78e+11 | normal
     16384 | 4.40e+12  8.80e+12  4.75e+12 | normal
     32768 | 3.52e+13  7.04e+13  3.32e+13 | strassen
     65536 | 2.81e+14  5.63e+14  2.33e+14 | strassen
    131072 | 2.25e+15  4.50e+15  1.63e+15 | strassen
    262144 | 1.80e+16  3.60e+16  1.14e+16 | strassen
    524288 | 1.44e+17  2.88e+17  7.98e+16 | strassen
   1048576 | 1.15e+18  2.31e+18  5.59e+17 | strassen
   2097152 | 9.22e+18  1.84e+19  3.91e+18 | strassen
   4194304 | 7.38e+19  1.48e+20  2.74e+19 | strassen
   8388608 | 5.90e+20  1.18e+21  1.92e+20 | strassen
  16777216 | 4.72e+21  9.44e+21  1.34e+21 | strassen
  33554432 | 3.78e+22  7.56e+22  9.39e+21 | strassen
  67108864 | 3.02e+23  6.04e+23  6.57e+22 | strassen
 134217728 | 2.42e+24  4.84e+24  4.60e+23 | strassen
 268435456 | 1.93e+25  3.87e+25  3.22e+24 | strassen
 536870912 | 1.55e+26  3.09e+26  2.25e+25 | strassen
1073741824 | 1.24e+27  2.48e+27  1.58e+26 | strassen

As we can see, with respect to additions only, Strassen outperforms the traditional normal matrix-multiplication with respect to number of additions, but only once your matrices exceed the size of roughly 30000x30000.

(Also note that the naive divide-and-conquer multiplication performs asymptotically the same, in terms of additions, as traditional matrix multiplication. However it still performs "worse" by initially a factor of 3, but as the matrix size increases, asymptotically worse by a factor of exactly 2 . Of course this tells us nothing about the true complexity which involves multiplications, but if it did, we might still want to use it if we had a parallel algorithm which could take advantage of the different computation structure.)

Answer 2

If are talking about the simple Divide and Conquer Matrix multiplication algo (and NOT the Strassens' method), then the number of operations are SAME as compared to the normal Matrix multiplication.

This link mentions:

In this case the divide-and-conquer approach leads to exactly the same number of operations as the "normal" method of matrix multiplication. The recurrence above comes from the fact that the normal method, when applied to 2-by-2 matrices, requires 8 multiplications and 4 additions.