Division

Division via Newton

Comparison

Matrix Multiplication

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 2: Division and Matrix Multiplication

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division I

First, we have to clarify what we shall mean by division.
Let numbers a, d ∈ N be given, where d , 0. There are two
versions of division; i.e., computing the quotient a/d andcomputing integers q, r such that a = qd + r and 0 6 r < d,respectively.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division I

First, we have to clarify what we shall mean by division.
Let numbers a, d ∈ N be given, where d , 0. There are two
versions of division; i.e., computing the quotient a/d andcomputing integers q, r such that a = qd + r and 0 6 r < d,respectively.
The second version (division with remainder) fits into the classof problems studied so far (n-bit numbers given as input aretransformed into output numbers having O(nc ) bits for aconstant c > 0 independently of n).

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division II

The first version does not fit directly into the class of problems
studied so far, since the quotient may have infinitely many bits.
Thus, it is only meaningful to require the computation of a
sufficiently precise approximation. Therefore, we first define
what is meant by approximation.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division II

The first version does not fit directly into the class of problems
studied so far, since the quotient may have infinitely many bits.
Thus, it is only meaningful to require the computation of a
sufficiently precise approximation. Therefore, we first define
what is meant by approximation.
Definition 1
Let x be any number. We say that x̃ is an approximation of x with
precision 2−c (precise for c bits) provided |x − x̃| 6 2−c .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division III

Then, the division problem is defined as follows:
Division
Input: Numbers a ∈ N, d ∈ N+ each having at most n bits.
Problem: Compute the quotient a/d with precision 2−n .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division III

Then, the division problem is defined as follows:
Division
Input: Numbers a ∈ N, d ∈ N+ each having at most n bits.
Problem: Compute the quotient a/d with precision 2−n .
Idea: We can split the problem into two subproblems; i.e.,
computing the inverse d−1 of d with precision 2−2n and thenmultiplying this approximation of d−1 and a.
In the following, we use d̃−1 to denote the approximationof d−1 with precision 2−2n .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division IV
Lemma 1 (Precision)
Let a, d be n-bit numbers. Suppose we have computed the inverse
d−1 of d with precision 2−2n . Then ad̃−1 is an approximation of a/dwith precision 2−n .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division IV
Lemma 1 (Precision)
Let a, d be n-bit numbers. Suppose we have computed the inverse
d−1 of d with precision 2−2n . Then ad̃−1 is an approximation of a/dwith precision 2−n .
Proof. Let d̃−1 be the approximation of d−1 with precision 2−2n .
By assumption, a < 2n , and thusa− ad̃−1d= |a||d−1 − d̃−1 |6 2n · 2−2n = 2−n .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division V
First, we deal with the computation of d−1 . One possible
approach would be to use the fact
1
1−x

=

∞
X

xi

provided |x| < 1 .

i=0

We can assume, without loss of generality, that 1/2 6 d < 1.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division V
First, we deal with the computation of d−1 . One possible
approach would be to use the fact
1
1−x

=

∞
X

xi

provided |x| < 1 .

i=0

We can assume, without loss of generality, that 1/2 6 d < 1.
n−1P
Proof. Let d =di 2i and let dk be the highest non-zero bit,i=0

i.e., dk , 0, k 6 n − 1 and dk+1 = · · · = dn−1 = 0 provided
k < n − 1. Then, d̂ =df d2−(k+1) satisfies 1/2 6 d̂ < 1. Thus, d̂
can be computed from d by applying a simple shift operation.
However, for determining k one needs O(n) bit operations in
the worst case.
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division VI

Now, since the inverse of 2−(k+1) is 2k+1 , knowing the inverseof d̂ with precision 2−2n is all we need. So, we can set x = 1 − d.
It remains to ask how many summands we actually have tocompute to achieve the desired approximation. The answer isprovided by the following lemma:

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division VII
Lemma 2Let d−1 be the exact inverse of d, where 1/2 6 d < 1. Furthermore,
2nP
let b2n =(1 − d)i . Then, we have |d−1 − b2n | 6 2−2n .
i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division VII
Lemma 2Let d−1 be the exact inverse of d, where 1/2 6 d < 1. Furthermore,
2nP
let b2n =(1 − d)i . Then, we have |d−1 − b2n | 6 2−2n .
i=0Proof. First, since 1/2 6 d < 1 we can conclude that∞P
0 < 1 − d 6 1/2. Thus, the geometrical series(1 − d)i is
i=0

absolutely convergent and from calculus we know that∞X
(1 − d)i =i=0

Therefore,

∞
P

1
1
= .
1 − (1 − d)d(1 − d)i is the exact inverse of d.

i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division VIII
Hence, we get|d−1− b2n | =

2n
∞
X
X
i
(1 − d)i(1 − d) −
i=0

i=0

=

∞
X

(1 − d)ii=2n+16∞X|(1 − d) | 6ii=2n+1=

Complexity and Cryptography

1−1+

 i
∞
X
1
2

i=2n+1
1 2n+12
1 − 21= 2−2n .

c Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton I

However, the resulting algorithm is quite slow compared tomultiplication.
Question
Can we do any better?

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton I

However, the resulting algorithm is quite slow compared tomultiplication.
Question
Can we do any better?

The affirmative answer is obtained as follows: We can avoid tocompute b2n+1 by evaluating the sum given above if we use
the well-known Newton procedure for computing zeros offunctions.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton II
Recall that for a given differentiable function f and x∗ withf(x∗) = 0, one can compute x∗ with any desired precision byusing

xk = xk−1 −f(xk−1 ),f 0 (xk−1 )(1)provided x0 is appropriately chosen. That is, then we know
from calculus thatlim xk = x∗ .
k→∞Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton II
Recall that for a given differentiable function f and x∗ withf(x∗) = 0, one can compute x∗ with any desired precision byusing

xk = xk−1 −f(xk−1 ),f 0 (xk−1 )(1)provided x0 is appropriately chosen. That is, then we know
from calculus thatlim xk = x∗ .
k→∞What is the appropriate f in our case?

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton III

In order to apply this method to our setting of computing theinverse, we cannot use f(x) = xd − 1. In this case, we would get
f 0 (x) = d, and thus for computing the iteration in (1), we
already should know d−1 .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton III

In order to apply this method to our setting of computing theinverse, we cannot use f(x) = xd − 1. In this case, we would get
f 0 (x) = d, and thus for computing the iteration in (1), we
already should know d−1 .
So, we set f(x) = d − 1/x, and obtain thus from (1) that thesequence (bk )k∈N defined by
bk = (2 − bk−1 d)bk−1(2)

converges to d−1 provided b0 is appropriately chosen.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division via Newton IV
Also, we should know that Newton’s procedure converges
quadratically. Thus, O(log n) iterations will suffice. For thesake of completeness, and for justifying our choice of b0 weinclude the following theorem here:
Theorem 1 (Number of Newton Iterations)
Let d be such that 1/2 6 d < 1, let b0 = 1 and let
bk = (2 − bk−1 d)bk−1 for all k > 1. Then we have
bk =

k −1
2X

(1 − d)i .

i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Proof I
Proof. We prove the theorem by induction. For the induction
base k = 1 we directly obtain
b1 = (2 − b0 d)b0 = 1 + (1 − d) =

1 −1
2X

(1 − d)i .

i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Proof I
Proof. We prove the theorem by induction. For the induction
base k = 1 we directly obtain
b1 = (2 − b0 d)b0 = 1 + (1 − d) =

1 −1
2X

(1 − d)i .

i=0

The induction step from k to k + 1 is derived as follows: We
have the induction hypothesis (abbr. IH)
bk =

k −1
2X

(1 − d)i .

i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Proof II

bk+1

= (2 − bk d)bk = 2bk − bk dbk
=

2bk −

k
2X
−1

i

(1 − d) · d ·

i=0

=

2bk +

k
2X
−1

(1 − d)i

k
2X
−1

i

(1 − d) (−1 + (1 − d))

i=0
2X
−1

(1 − d)i=0Complexity and Cryptography

k
2X
−1

(1 − d)i

i=0
2X
−1
k

k

= 2bk −( by the IH)

i=0

i

i

(1 − d) +

i=0

2X
−1
k

i+1

(1 − d)

i=0

k
2X
−1

(1 − d)i

i=0

c Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Proof III=

2bk − bk −+ (1 − d)

2k

k
2X
−1

k
2X
−1

i=1

i=0

(1 − d)i(1 − d)i +

k
2X
−1

k
2X
−1

i=1

i=0

(1 − d)i(1 − d)ik2X−1(1 − d)i

i=0
2X
−1
k

=

bk +

k

(1 − d)2 +i

i=0

=

k
2X
−1

(1 − d)i +

2k+1
X−1

by the IH

i=2k

i=0

=

(1 − d)i

2k+1
X−1(1 − d)i .

i=0Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division XIII

The latter theorem essentially shows that the number of correct
bits is doubled in each iteration.
Summarizing the results obtained so far, now we can prove thefollowing theorem: In the following M(n) denotes an upperbound on the time needed to do a multiplication of two n-bit
numbers.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division XIII

The latter theorem essentially shows that the number of correct
bits is doubled in each iteration.
Summarizing the results obtained so far, now we can prove thefollowing theorem: In the following M(n) denotes an upperbound on the time needed to do a multiplication of two n-bit
numbers.
Theorem 2
There is an algorithm which, on input any two numbers a and dhaving at most n bits, computes the quotient a/d with precision 2−nusing time O(M(n) log n).

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division XIV
Proof. First, using Theorem NNI we can compute the inverse
d−1 of d with precision 2−2n by using dlog 2ne + 1 many
iterations. In each iteration we have to perform two
multiplications and one addition. The two multiplications
require time O(M(n)) and the addition needs time O(n). Of
course, we have to truncate the result of each iteration to the 2nleading bits.
Furthermore, by Lemma (Precision), it then suffices to multiply
a and the approximate inverse. This requires anothermultiplication of two numbers having at most 2n bits. Thus,
the overall time complexity is O(M(n) log n).

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Discussion I
Does this mean that division is more complex thanmultiplication?

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Discussion I
Does this mean that division is more complex thanmultiplication?
We may be tempted to answer this question affirmatively, butsome care has to be taken here. Of course, we can try to prove alower bound on the number of bit operations needed toperform division. Provided we could show this lower bound tobe Ω(M(n) log n), we are done in the sense that we then know
no improvement is possible. But this is much easier said thandone. Proving non-trivial lower bounds is a very hard task
(and we still have almost no experience in doing so). Second,
we could try to find another method for division. But again,
this is easier said than done. Nevertheless, we could try it.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Discussion II

Finally, it is well possible that we have already collected all
good ideas needed, but failed to put them together in the rightway. Maybe, we have been a bit too generous. The point here isthat we always perform multiplications and additions of 2n-bit
numbers.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Discussion II

Finally, it is well possible that we have already collected all
good ideas needed, but failed to put them together in the rightway. Maybe, we have been a bit too generous. The point here isthat we always perform multiplications and additions of 2n-bit
numbers.
Taking into account that the Newton procedure is self-correcting,
Cook (1966) observed that we can ignore the bits that are
anyhow not correct. That is, instead of performing
multiplications and additions of 2n-bit numbers we only use
the highest 2k bits in iteration k when executing (2).

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Discussion III
We illustrate the idea below. In our example we set d = 0.66
and assume that we need the first 8 digits to be correct. Thus,
we have to compute 1.5151515 (we perform the calculation here
in decimal notion). The left column shows the results whenalways 8 digits are used, while the right column displays theresult when using 2, 4, and 8 digits.

b1
b2
b3
b4
b5

8 digits
1.34
1.494904
1.5148809
1.5151514
1.5151515

2k digits
1.4
1.506
1.5150962
1.5151515
1.5151515

This looks pretty good.
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division versus Multiplication I
Now we can establish the complexity of division relative to
multiplication.
We make the following assumptions about the function M(n):First, we assume M(n) > n for all n ∈ N+ and that
M(m) 6 M(n) for all m, n ∈ N+ provided m 6 n. Second, we
assume that M(n) = ng(n), where g : N → N is a function
satisfying g(n) > 0 and g(m) 6 g(n) for all m, n ∈ N+
whenever m 6 n. Note that the given upper bounds M(n)satisfy these assumptions.
Consequently, assuming m 6 n, we obtain
mg(m) + ng(n) 6 mg(n) + ng(n) = (m + n)g(n)6 (m + n)g(m + n) .
This in turn implies that
M(m) + M(n) 6 M(m + n)Complexity and Cryptography

for all m, n ∈ N+ .

(3)
c Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division versus Multiplication II

Let I(n) denote the time needed to compute the inverse of any
n-bit number with precision 2−2n . Using the ideas justexplained, we obtain the following theorem:

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division versus Multiplication II

Let I(n) denote the time needed to compute the inverse of any
n-bit number with precision 2−2n . Using the ideas justexplained, we obtain the following theorem:
Theorem 3
There exists a constant c > 0 such that I(n) 6 c · M(n) for
all n ∈ N+ .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division versus Multiplication II

Let I(n) denote the time needed to compute the inverse of any
n-bit number with precision 2−2n . Using the ideas justexplained, we obtain the following theorem:
Theorem 3
There exists a constant c > 0 such that I(n) 6 c · M(n) for
all n ∈ N+ .
Proof. We execute the iteration given in (2), but use only thehighest 2k bits of d and bk−1 for computing bk , where again
b0 = 1, and k = 1, . . . , dlog 2ne + 1. The result is then truncatedto the highest 2k+1 bits.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Division versus Multiplication III
Each iteration needs two multiplications and one addition. So,
we can uper bound the complexity of iteration k by c̃ · M(2k )for a suitable constant c̃ > 0. Using (3) we thus obtain
I(n) 6 c̃ · (M(2) + · · · + M(2log 2n+1 )) 6 c̃ · M(ĉn) .
Since M(n) 6 n2 , we have c̃ · M(ĉn) 6 c̃ · ĉ2 M(n), and thus, itsuffices to set c = c̃ · ĉ2 .
Now one has to show that the sequence (bk )k∈N computed in
the way described above converges to the inverse of d and that
we have to compute only the first dlog 2ne + 1 members of it.
This is left as an exercise.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication I

Next, we turn our attention to another fundamental problem,i.e., matrix multiplication. Matrix multiplication is needed innumerous applications involving linear algebra. Therefore,
studying the complexity of matrix multiplication is not only of
theoretical interest but also of fundamental practicalimportance.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication I

Next, we turn our attention to another fundamental problem,i.e., matrix multiplication. Matrix multiplication is needed innumerous applications involving linear algebra. Therefore,
studying the complexity of matrix multiplication is not only of
theoretical interest but also of fundamental practicalimportance.
In order to achieve as much generality as possible, we shallconsider matrix multiplications for any matrices defined over aring.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication II
Definition 2
Let S be any non-empty set containing at least two distinguishedelements 0 and 1, and let + and · be binary operations over S (that is+ : S × S → S and · : S × S → S). Then R = (S, +, ·, 0, 1) is a ring withidentity element provided that for all a, b, c ∈ S the following
properties hold:(1) (a + b) + c = a + (b + c) and (a · b) · c = a · (b · c);(2) (a + b) = (b + a) (+ is commutative);(3) (a + b) · c = a · c + b · c and a · (b + c) = a · b + a · c;(4) a + 0 = 0 + a = a (0 is the neutral element with respect to +);(5) a · 1 = 1 · a = a (1 is the identity element with respect to · );(6) For each a ∈ S there exist an element −a ∈ S such thata + (−a) = (−a) + a = 0 ( −a is the additive inverse of a).
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication III

Since we only consider rings with identity, we refer to a ringwith identity as to a ring for short.
Furthermore, if R is a ring and the operation · is commutative,then we say that the ring R is commutative. Finally, if R is acommutative ring and if for every a ∈ S \ {0} there exist anelement a−1 ∈ S such that a · a−1 = a−1 · a = 1, then R is said tobe a field.
So, let R = (S, +, ·, 0, 1) be a commutative ring with 1.
Furthermore, let n ∈ N+ . We consider the set Mn of all n × nmatrices over R.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication IV

Moreover, let
1 0 · · · 0 0 1 · · · 0 


 ·
· 


In = 
· 

 ·
 ·
· 
0 0 · · 0 1
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication V

andComplexity and Cryptography
0 · · · 0
 ·
· 



· 
0n =  · ·· 
0 · · · 0c Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication VI
Addition and multiplication of matrices from Mn is defined as
usual by using the addition and multiplication from theunderlying ring R. We denote the resulting operations by +n
and ×n , respectively. That is, for A = (aij ) and B = (bij ),i, j = 1, . . . , n, the sum A +n B is the n × n matrix C and the
product A ×n B is the n × n matrix D defined by
A +n B =df C,

where cij = aij + bij

A ×n B =df D,

where dij =nXi, j = 1, . . . , n ;aik · bkj

i, j = 1, . . . , n .

k=1Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication VII
The following important property is stated as an exercise:
Exercise 1. Let Mn = (Mn , +n , ×n , 0n , In ). Then we have: Mn isa ring if and only if R is ring.
Note that we did not require the ring R to be a commutative
one in Exercise 1. It should be noted that the matrix
multiplication ×n as defined above, is not commutative forn > 1, even if the multiplication · in the underlying ring R iscommutative. In the following, we often omit the subscript n in
+n and ×n , i.e., we just write + and ×, when there is no
possibility of confusion. Moreover, we often just write AB
instead of A × B to simplify notation.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication VII
The following important property is stated as an exercise:
Exercise 1. Let Mn = (Mn , +n , ×n , 0n , In ). Then we have: Mn isa ring if and only if R is ring.
Note that we did not require the ring R to be a commutative
one in Exercise 1. It should be noted that the matrix
multiplication ×n as defined above, is not commutative forn > 1, even if the multiplication · in the underlying ring R iscommutative. In the following, we often omit the subscript n in
+n and ×n , i.e., we just write + and ×, when there is no
possibility of confusion. Moreover, we often just write AB
instead of A × B to simplify notation.
Next, we continue with a very useful technical result. Let R be acommutative ring with 1, and let Mn be the ring of all n × nmatrices over R.
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication VIII
Assume n to be even. Then, we can divide any n × n matrix A into 4
matrices A11 , A12 , A21 , A22 of size n/2 × n/2, i.e.,a11···
a1, n2

·


·


·

 a n2 1···
a n2 , n2=  an 2 +1,1 · · · a n2 +1, n2

·


·


·
an1
···
an, n2
A11 A12=.
A21 A22A

Complexity and Cryptography

a1, n2 +1···

a n2 , n2 +1
a n2 +1, n2 +1

···
···

an, n2 +1

···


a1n

·


·


·

a n2 n 
a n2 +1,n 


·


·


·
ann

c Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication IX

Furthermore, let R2,n/2 be the ring of all 2 × 2 matrices with elementsfrom Mn/2 . Then, the multiplication and addition of matrices from
Mn is equivalent to the multiplication and addition of thecorresponding 2 × 2 matrices from R2,n/2 . That is, for A, B ∈ Mn and
A11 , A12 , A21 , A22 B11 , B12 , B21 , B22 ∈ R2,n/2 we have
A11 + B11 A12 + B12
A+B =
(4)
;
A21 + B21 A22 + B22
A11 B11 + A12 B21 A11 B12 + A12 B22
A×B =
.
(5)
A21 B11 + A22 B21 A21 B12 + A22 B22Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication X
Now, we are ready to deal with the complexity of matrix
multiplications. What we are going to count here is the numberof the arithmetic ring operations, i.e., additions andmultiplications in the underlying ring R. Our first theorem
establishes the starting point by analyzing the obvious matrix
multiplication algorithm that is based on the definition of
matrix multiplication.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication X
Now, we are ready to deal with the complexity of matrix
multiplications. What we are going to count here is the numberof the arithmetic ring operations, i.e., additions andmultiplications in the underlying ring R. Our first theorem
establishes the starting point by analyzing the obvious matrix
multiplication algorithm that is based on the definition of
matrix multiplication.
Theorem 4
The usual algorithm for multiplying any two n × n matrices requires
2n3 − n2 arithmetic operations.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XI
Proof. Let A = (aij ) and let B = (bij ), i, j = 1, . . . , n be any twon × n matrices. Then the product C = (cij ) = A × B is given by
cij =

n
X

aik bkj .

k=1

That is, the computation of every element cij requires n ring
multiplications and n − 1 ring additions. Since there are n2
many elements cij which have to be computed, the total
number of ring multiplications is n3 and the total number ofring additions is n2 (n − 1). Thus the overall number of ring
operations is 2n3 − n2 .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XII

Question
Can we do any better?

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XII

Question
Can we do any better?

The affirmative answer was found by Volker Strassen.
Theorem 5 (Strassen (1969))
There is an algorithm for multiplying any two n × n matrices that
requires O(nlog 7 ) ring operations.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XIII
Proof. Let T (n) denote the number of ring operations needed for
multiplying any two n × n matrices. Furthermore, let
A, B ∈ Mn be any two n × n matrices. First, we assume n to bea power of 2. Using Equation (5) we can write
C = A×B

A11 B11 + A12 B21 A11 B12 + A12 B22=
A21 B11 + A22 B21 A21 B12 + A22 B22
C11 C12=
C21 C22
This approach alone does not help, since we have reduced theoriginal problem of size n into eight subproblems of size n/2.
Thus, the resulting recursive equation has the solution
T (n) = O(nlog 8 ) = O(n3 ).
Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XIV
At this point Strassen (1969) discovered the following: Let

M1 = (A12 − A22 )(B21 + B22 )M2 = (A11 + A22 )(B11 + B22 )M3 = (A11 − A21 )(B11 + B12 )
M4 = (A11 + A12 )B22
M5 = A11 (B12 − B22
M6 = A22 (B21 − B11 )M7 = (A21 + A22 )B11 ,Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XV

then an easy calculation shows that
C11 = M1 + M2 − M4 + M6
C12 = M4 + M5
C21 = M6 + M7
C22 = M2 − M3 + M5 − M7 .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XV

then an easy calculation shows that
C11 = M1 + M2 − M4 + M6
C12 = M4 + M5
C21 = M6 + M7
C22 = M2 − M3 + M5 − M7 .
Thus, we have reduced the original problem of size n to sevenmultiplications of matrices having size n/2 × n/2 and 18
additions of n/2 × n/2 matrices.

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XVIConsequently, for n > 2 we directly get the recursive equation
T (n) = 7 · T

n
2

+ 18

 n 22,

which has the solution T (n) = 7 · 7log n − 6n2 , and hence
T (n) = O(7log n ) = O(nlog 7 ).
If n is not a power of 2, then we embed each matrix in a matrix
whose dimension is the next-higher power of 2. This at most
doubles the dimension and thus increases the constant by atmost a factor of 7. Hence, T (n) = O(nlog 7 ) for all n ∈ N+ .

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Matrix Multiplication XVIIStrassen’s (1969) matrix multiplication algorithm is also not thebest possible. After his pioneering paper, many researchers
worked on even faster matrix multiplication algorithms. The
currently best known algorithm achievesO(n2.376 )and is due to Coppersmith and Winograd (1990).

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix MultiplicationEnd

Sir Isaac Newton

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Stephen A. Cook

Complexity and Cryptographyc Thomas Zeugmann

Division

Division via Newton

Comparison

Matrix Multiplication

End

Volker Strassen

Complexity and Cryptographyc Thomas Zeugmann