In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

Computer Science Asked by retsek680 on February 4, 2021

In Strassen’s algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?

Hi, I was reading this question but I do not follow Yuval Filmus’s answer completely.

He offers two ways of padding the matrix with zeroes, I am interested in his first suggestion, padding the entire matrix with zeroes at the start such that the new matrix has dimensions $Ntimes N$ where $N = 2^c$.

He says "$N < 2n$ so this doesn’t affect the asymptotic complexity."

Could someone please elaborate as I do not follow, I understand calculating time complexity with the master theorem and $T(n) = aT(n/b) + f(n)$ so if someone could explain how this works in reference to that it would be greatly appreciated.

One Answer

Suppose that if $N = 2^c$ then you can multiply two $N times N$ matrices in time $O(N^{log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{log_27}$.

Now suppose that we are given two $ntimes n$ matrices. We pad them to $N times N$ matrices, where $N = 2^{lceil log_2 n rceil} < 2n$. We can extract the product of the original matrices from the product of the new matrices. The two new matrices can be multiplied using at most this many operations: $$ CN^{log_2 7} < C (2n)^{log_2 7} = 7C n^{log_2 7} = O(n^{log_2 7}). $$

Answered by Yuval Filmus on February 4, 2021

Add your own answers!

Related Questions

Design of a synchronized clock

0  Asked on October 21, 2021 by ahmedou


How private IP address is determined?

1  Asked on October 21, 2021 by nurin-izzati-jafri


Race Condition in Mesa Monitor

0  Asked on October 21, 2021 by heroman


Counting one’s in a stream of bits

0  Asked on October 21, 2021 by srajan


Find original array from array with pairs of adjacent elements

1  Asked on October 21, 2021 by james-flanagin


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP