In class, we saw Karatsuba$$s algorithm which was a way to speed up the computation of a $$ b

for two n$-$bit integers a and b$.$ In this problem, we analyse an algorithm for multiplying two

$2$

CSC$236$H$1$Y $20245$ Last updated: July $4,2024$

upper$-$triangular $1$ matrices abbreviated UT matrices. See Algorithm $2.$ The standard approach for

multiplying two matrices is shown below for two $2\backslash$times $2$ matrices.

A $$ B $=$

a$1,1$ a$1,2$

a$2,1$ a$2,2$

$$

b$1,1$ b$1,2$

b$2,1$ b$2,2$

$=$

a$1,1$b$1,1+$ a$1,2$b$2,1$ a$1,1$b$1,2+$ a$1,2$b$2,2$

a$2,1$b$1,1+$ a$2,2$b$2,1$ a$2,1$b$1,2+$ a$2,2$b$2,2$

For ease of explanation, if the inputs A and B to Algorithm $2,$ Algorithm $3,$ and Algorithm $4$ have

dimension n $\backslash$times n$,$ then let n be a power of two. In practice, we can always pad the matrix with

rows and columns of all zeros so that this is the case.

Note that the notation A$[$i : j$,$ : k$]$ represents the submatrix of A consisting of the rows i to j

inclusive and columns $$ to k inclusive. For A and B$,$ let A$11=$ A$[1$ : n$/2,1$ : n$/2],$ A$12=$ A$[1$ :

n$/2,($n$/2+1)$ : n$],$ A$21=$ A$[($n$/2+1)$ : n$,1$ : n$/2],$ and A$22=$ A$[($n$/2+1)$ : n$,($n$/2+1)$ : n$].$ Bij

are defined similarly for i$,$ j in $[2].$

The time it takes to multiple two constant dimension matrices is constant time.

Algorithm $2$ multiplyTT$($A : UT matrix, B : UT matrix$)->$ UT matrix

Require: A and B are two upper$-$triangular matrices.

Ensure: Outputs A $$ B$.$

$1$: if n $=1$ then return A $$ B

$2$: end if

$3$: M$1$ multiplyTT$($A$11,$ B$11)$

$4$: M$2$ multiplyTM$($A$11,$ B$12)+$ multiplyMT$($A$12,$ B$22)$

$5$: M$3$ multiplyTT$($A$22,$ B$22)$

$6$: return

M$1$ M$2$

$0$ M$3$

Algorithm $3$ multiplyTM$($A : UT matrix, B : matrix$)->$ matrix

Require: A is an upper$-$triangular matrix and B is a matrix.

Ensure: Outputs A $$ B$.$

$1$: if n $=1$ then return A $$ B

$2$: end if

$3$: M$1$ multiplyTM$($A$11,$ B$11)+$ multiply$($A$12,$ B$21)$

$4$: M$2$ multiplyTM$($A$11,$ B$12)+$ multiply$($A$12,$ B$22)$

$5$: M$3$ multiplyTM$($A$22,$ B$21)$

$6$: M$4$ multiplyTM$($A$22,$ B$22)$

$7$: return

M$1$ M$2$

M$3$ M$\backslash$