What are we looking at?

> I don't see how you would recover the value a0b0+a1b1+a2b2 from the mess on the right side.
Probably something to do with making the f[i,j] coprime. The first three are clearly coprime, and the last three could be made coprime with an appropriate choice of primes.

> And he claims there are only two "multiplications" on the right side,
The two multiplications are
> (a0p0 + a1p1 + a2p2)(b0p3 + b1p4 + b2p5)
and
> (a0p3 + a1p4 + a2p5)(b0p0 + b1p1 + b2p2)

Multiplication by p_i isn't counted because that's O(n^2) (assuming an nxn matrix).

So it appears to involve encoding each row or column as a number, multiplying the numbers, then extracting the individual products from the result. In which case, it presumably only works for integer matrices.

Also, it's not clear whether it's only O(n^2) "multiplies", ignoring the fact that you'll be multiplying larger numbers.

>the 3^m multiplications can be converted to (2^m)*(2m + 5 choose 5) multiplications.
>when m = 100, 3^m < (2^m)*(2m + 5 choose 5)
what the fuck, he is saying that its more efficient not to convert the problem at all.

...

I'm going to read it over this weekend, exciting times ahead if it's real. From what I skimmed so far, the matrix has to be ass huge, though.

Does
[math] {200 + 5 \choose 5} [/math] actually mean 205 choose 5 or do those parenthesis mean something differnet in a linear algebra context? If it's just the choose function, why not just write 205 instead of 200 + 5? I feel like I'm missing something

(I probably fucked up the latex, but you can figure out what I meant)

>arxiv.org/abs/1612.04208

I'm unsure of whether this person is claiming a general algorithm... the constants '5', '6,' '100,' and '200' seem oddly specific for general n-by-n matrices.

it says 2m+5

It means 205 choose 5. It's just written that way to make it clear that it's 2m+5 choose 5 for m=100.

It should be made clear that we're talking about insanely large numbers here; for m=100
2^m*C(2m+5,5) = 3641210728011992739223798844639900860416
3^m = 515377520732011331036461129765621272702107522001

It's not practical to actually perform that many multiplications, even if you had the entire world's computing power at your disposal.

>Is anyone else actually trying to read this? I'm very confused by formula (3)

Just wait till you see formula (8) and onward

> Multiplication by p_i isn't counted because that's O(n^2)

ok that makes sense

> something to do with making the f[i,j] coprime

that's originally what i was thinking, but it actually looks like he doesn't extract the coefficients directly. Instead he sets up a matrix equation Ma_I=F for the vector a_I of unknown coefficients, and then getting the product of the vectors is just a matter of adding up the coefficients in a_I that don't correspond to cross terms.

Although it seems he works one row and column at a time, so I don't quite understand how he gets On^2 for two square matrices.

Thanks

>mfw

Brainlets, leave

>spend five years on improving matrix multiplication
>come up with algorithm that is optimal
>8 pages of hideous index notation
bruh

bullshit no algorithm has been discovered that is faster than O(n^2).

obviously...

You first have to read the matrix to do anything with it. There is absolutely no way you could read a matrix faster than O(n^2).
t. not even a computer scientist.

nobody is claiming otherwise

Isn't the article though?

I mean if a whole multiplication were O(n^2) it would require read to be less than O(n^2)

no

Shit I confused read with a memory lookup.

Sorry tery, plz don't bully me

another episode of "millenial frogposter embarasses himself on Veeky Forums"

you faggots keep on masturbating in your big O train while I drive by you on a 10000mph cache optimized motorcycle yelling "fuck you" into your monkey ears

It's bullshit. Plenty of dumbasses try to publish shit.

lucatrevisan.wordpress.com/2016/12/14/matrix-multiplication-not-yet-doable-in-quadratic-time/

What is sad is that the author explicitly states that they took 5 years to do this.
If this is true then it's really a pity.

>muh [math]O(n^{whatever})[/math]
this is why nobody takes pure mathematics seriously, because things may work as fast as they claim, but it 45 dimensional universe

bull fucking shit, calling, branch misprediction is fucking expensive and so is accessing ram
it reminds me when i was reading about guy whose matri-mullibrary was 10x faster because of SIMDfication

i know some of these algorithms don't actually provide extra speed unless the matrix is the size of your mom

is it efficient enough to be used in stuff like machine learning where you usually have medium-large matrices?

is it even real?

if he just locked himself in his room without ever consulting experts in the field, it's his own fucking fault.
math is complicated, you should be humble enough to accept that

O(n^2 + n^2) = O(n^2)

scottaaronson.com/blog/?p=3054

Doesn't seem good (see comments 35 and 40).

If the things you're doing can be done with a cache then they're probably trivial babby shit anyways.

You don't know how cache works, do you?

>ywn slap down a 5 page thesis on the profs table and just walk away knowing that they will call you.

O(n^2 + n^2) = O(n^2)
O(n^2) + O(n^2) = O(n^2)
2 * O(n^2) = 1 * O(n^2)
2 = 1

So this is the standard of math in CS.
It's no wonder that they're still having problems settling P=NP.

"O" is a function that takes a function and returns a set of functions that are bounded asymptotically by a constant multiplied by that function; O(a) + O(b) is a completely meaningless statement, and certainly doesn't equal O(a+b).

With that said, it's really stupid how computer scientists use = as opposed to ∈ in this instance.

dude...

Not all computer scientists use equality as opposed to set membership. You're right that we abuse notation often, but, in my case, I only really perform rigorous analysis to justify things that I'm doing in practice. In the end, I care more about the result than the symbols I'm writing in Latex.

The best part of this post is the fact that P versus NP is posed with respect to asymptotic big-O notation. Stay classy, /sci.

It's easier to write and everybody understands it.