Skip to main content
20 votes
Accepted

In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n). That is wrong. It might work for a small ...
Jakube's user avatar
  • 1,585
13 votes
Accepted

Proof that no O(n) multiplication algorithm exists

There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.
Yuval Filmus's user avatar
9 votes

Proof that no O(n) multiplication algorithm exists

No nontrivial lower bound for the multiplcation is known (clearly, it is $\Omega(n)$) and David Harvey himself does not know if a complexity of $O(n\log(n))$ is the best possible: in his own words: "...
user6530's user avatar
  • 954
9 votes

In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Short answer: because it's natural and convenient. Longer answer: The number of multiplications to multiply a matrix of size p,q with a matrix of size q,r is pqr with a naive algorithm, and something ...
Stef's user avatar
  • 530
6 votes
Accepted

Could all CPU instructions get fundamentally faster if a better multiplication method was developed

I don't see the relevance. New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with ...
David Richerby's user avatar
6 votes

Lower Bound of Matrix Multiplication

Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system ...
Yuval Filmus's user avatar
6 votes

In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

For n = 100, the naive algorithm takes 1,000,000 multiplications and almost as many additions. If we let n = number of rows / columns, then it takes $n^3$ multiplications and $n^3 - n^2$ additions. If ...
gnasher729's user avatar
  • 30.6k
5 votes

Why don't integer multiplication algorithms use lookup tables?

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers ...
D.W.'s user avatar
  • 162k
5 votes

Karatsuba multiplication on numbers with odd length

Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ : $a = 2 * 10^2 + 34$ and $b = 8 * 10^2 + 57$ ; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$. It ...
Roukah's user avatar
  • 771
4 votes
Accepted

$(max,+)$ matrix product with limited number of values

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. ...
Discrete lizard's user avatar
  • 8,303
4 votes

Number of computations for multiplication

From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have ...
Daniel McLaury's user avatar
4 votes
Accepted

Number of computations for multiplication

It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.
Rick Decker's user avatar
  • 14.8k
4 votes

Last digit of polynomial value

Remainder modulo 10 instead of last digit What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10. For simplicity, we will compute the ...
John L.'s user avatar
  • 39.1k
4 votes

Difficulty understanding the faster multiplication hardware

You want to multiply x by y, where both are 32 bit numbers. The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 ...
gnasher729's user avatar
  • 30.6k
4 votes

Could all CPU instructions get fundamentally faster if a better multiplication method was developed

No, it's not helping. You can do n bit multiplication in O (log n) time, not O (n log n). The only problem is that you need an enormous amount of hardware to do this, growing as O (n^2), while this ...
gnasher729's user avatar
  • 30.6k
4 votes
Accepted

Why don't integer multiplication algorithms use lookup tables?

Some integer multiplication algorithms do use lookup tables. The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a ...
David Cary's user avatar
4 votes
Accepted

Matrix chain multiplication: Greedy approach

Consider the product $ABC$, where $A$ is $5\times 2$ $B$ is $2\times 3$ $C$ is $3\times 100$ Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 ...
Yuval Filmus's user avatar
4 votes
Accepted

Complexity of multiplying bivariate polynomials of degree n

It suffices to describe how to evaluate $P(\omega^u,\omega^v)$ at the roots of unity. Suppose $P(X,Y)=\sum_{i,j} a_{i,j} X^i Y^j$. Let $$F_{b,c}(X,Y) = \sum_{i,j} a_{2i+b,2j+c} X^i Y^j$$ where the ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Swap elements using integer addition and multiplication gates

Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this: ...
orlp's user avatar
  • 13.6k
3 votes

Is there any bitwise multiplication algorithm that is sub O(n^2)?

Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.
Artem Plotkin's user avatar
3 votes
Accepted

Necessity of convolution operations for product of two polynomials via brute force method

Given two polynomials $P_n(x)$, $Q_n(x)$, you can obviously calculate the value $P_n(x) · Q_n(x)$ in $O(n)$ for every x. The document asks about calculating the coefficients, which is a very different ...
gnasher729's user avatar
  • 30.6k
3 votes

Necessity of convolution operations for product of two polynomials via brute force method

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} ...
Peter Taylor's user avatar
  • 2,082
3 votes
Accepted

Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The ...
Yuval Filmus's user avatar
3 votes

Lower bound on multiplication

There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.
Manuel Cáceres's user avatar
3 votes

Karatsuba Multiplication Rule in dividing a Number in two parts

The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for x = 12345 y = 2478 you would ...
Tom van der Zanden's user avatar
3 votes

Is matrix multiplication cheaper than inverse?

Matrix multiplication and matrix inverse have the same asymptotic running time. If we denote the running time of multiplying two $n \times n$ matrices by $T_1(n)$, and that of inverting an $n \times n$...
Yuval Filmus's user avatar
2 votes

Karatsuba Multiplication with n/3 division of large number

The algorithm you are looking for seems to be the Toom-3 algorithm.
Yuval Filmus's user avatar
2 votes

Linear time multiplication on RAM machine?

The page is not fooling you. I'll refer you to the original paper, but accordingly they show the following: Theorem 6.1 There exists an SMM which performs integer-multiplication in linear time, i.e....
ryan's user avatar
  • 4,511
2 votes

An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

One algorithm to compute inverses in a finite field is to raise to a large power. In particular, $x^{-1} = x^{p-2}$ if you are working in $\mathbb{F}_p$ (by Fermat's little theorem). You can use ...
D.W.'s user avatar
  • 162k
2 votes

An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible