Talk:Computational complexity of matrix multiplication

Merge from Matrix multiplication algorithm

I propose merging Matrix multiplication algorithm into Computational complexity of matrix multiplication. I think the content in Matrix multiplication algorithm can easily be explained in the context of Computational complexity of matrix multiplication, and a merger would not cause any article-size or weighting problems in Computational complexity of matrix multiplication.129.177.124.226 (talk) 12:12, 27 September 2021 (UTC)

I think this might be a good idea. From my perspective, the theoretical computer science question of sub-cubic algorithms is a topic of interest meriting its own article, with questions of distributed algorithms and cache behavior being more secondary. However, I think this might not be a consensus belief, which is why I separated sub-cubic algorithms into its own article Computational complexity of matrix multiplication rather than restructuring Matrix multiplication algorithm. In any case, a merge is appropriate if having both articles seems redundant. Fawly (talk) 19:55, 29 September 2021 (UTC)

• Oppose: Each article is already quite long and complex, and merging them into one just makes reading them that much more tedious. Wikipedia is not a collection of review articles of unbounded length, building on an assumption that the reader has the leisure time, patience and mental fortitude to plow through a long article. Let each article say what it needs to say, succinctly. If two articles have overlapping subject matter, that's OK; the minority of readers who need both can go ahead and read both. Similar remarks for article editors and maintainers: the burden of tracking two smaller articles is lower than the burden of maintaining one large article in a coherent, well-organized state. 67.198.37.16 (talk) 18:34, 31 January 2022 (UTC)

Closing, given the uncontested objection with stale discussion. Klbrain (talk) 08:55, 1 October 2022 (UTC)

Maximum Matrix Efficiency Constant

/It seems like there is a limiting value to how efficiently two matrices can be multiplied by each other. I am wondering if this is a mathematical constant, similar to how e is the limit of the sum of x^n/n! infinite series. ScientistBuilder (talk) 02:12, 13 March 2022 (UTC)

There is a limiting value (typically denoted ω in the literature) but my understanding is that many researchers think or hope that ω = 2, making this a somewhat uninteresting mathematical constant to name. Fawly (talk) 07:40, 13 March 2022 (UTC)

AlphaTensor

Are we going to add the latest scientific result obtained by Google deepmind? 161.81.69.23 (talk) 16:31, 24 November 2022 (UTC)

It's probably sufficiently notable, but it has no direct implications on the matrix multiplication exponent. There's currently no section about matrix multiplication algorithms in various bases, which would be a good place to put it. Fawly (talk) 04:28, 27 November 2022 (UTC)

Feasible matrix multiplication, vs galactic algorithms

The article contained nothing about galactic size algorithms and that there are also available usable ones. I added sentence about it, but is was (not) corrected, but changed to:

"On the opposite, above Strassen's algorithm of 1969, and Pan's algorithm of 1978, whose respective exponents are slightly above and below 2.78 have constant coefficients that make them feasible."

Above sentence in its very language layer does not make a sense at all. Also scientifically does not.

I AM RISING IT, BECAUSE MR D.LAZARD CHANGED MY INITIAL, SENSIBLE VERSION, TO NON-SENSE. AND AT MY PERSONAL SITE MR D.LAZARD WRITES THAT IT SHOULD BE DELETED.

To repeat what D Lazard wrote: "above and below 2.78 have constant coefficients that make them feasible.". What does it mean ???? Thus I suggest Mr Lazard not insinuate to delete my personal page. It should be augmented, ok. Jerzy.Respondek (talk) 10:44, 18 December 2024 (UTC)

Sorry, I forgot a comma; this is presently fixed. The sentence must be read as "On the opposite, above Strassen's algorithm of 1969 and Pan's algorithm of 1978, whose respective exponents are slightly above and below 2.78, have constant coefficients that make them feasible."

By the way, it is your right to prefer Pan's algorithm to Strassen's one. But, Strassen's algorithm is presently used in some implementations, while, as far as I know, this is not the case of Pan's algorithm. So, there is no reason for giving an undue weight to Pan algorithm by not mentioning Strassen's one in this sentence.

Also, there is no personal site in Wikipedia. See WP:OWN that begins with All Wikipedia pages and articles are edited collaboratively by the Wikipedian community of volunteer contributors. No one, no matter what, has the right to act as though they are the owner of a particular article (or any part of it). Even a subject of an article, be that a person or organization, does not own the article, nor has any right to dictate what the article may or may not say. No one, whether a subject or an article creator, has a responsibility to maintain an article or can normally be held responsible for its content.

I never insinuate anything. The truth is that I asked the community of Wikipedia editors whether the page about you should be deleted. So far, all intervening editors (except you) agree that this page must be deleted. D.Lazard (talk) 13:29, 18 December 2024 (UTC)

> "So, there is no reason for giving an undue weight to Pan algorithm by not mentioning Strassen's one in this sentence."

I definitely agree. The science development is step by step, at first must be Strassen with 2.807, only later comes Pan with better exponent, around 2.77, but still not "galactic". Also importantly, there are no better results than Pan's which are feasible.

> "On the opposite, above Strassen's algorithm of 1969 and Pan's algorithm of 1978, whose respective exponents are slightly above and below 2.78, << have constant coefficients that make them feasible.>>"

The second part <<...>> of the sentence is still:

- not readable to a typical wiki reader at all

- contains hidden context, clear only for specialists. (off-topic: My book is intended just for non-specialists, and even non-mathematicians, e.g. engineers in my opinion will be able to understand it if they will want so. Used math tool are as complex as necessary, but no more.)

Thus Mr Lazar Your sentence still does not comply with certain wiki guideline.

----Deletion of personal page-------------------------------------------------------------

> "The truth is that I asked the community of Wikipedia editors whether the page about you should be deleted. So far, all intervening editors (except you) agree that this page must be deleted."

They got a superficial impression, so for such a case is just a discussion. Look at the holes I filled in a few articles on elementary topics. The area of confluent Vandermonde matrix is too less known up to now. I shall give only one example: it is usable even is such an elementary methods like solving recursive equations by matrix tools. My arXiv work (waiting for review now) enumerates above a dozen (revision will have even more) of elementary applications. But what we have now, in wiki (But already I corrected two articles) and not only in wiki ? Authors are pretending that the case of multiple nodes in Vandermonde does not exists... But the theory on that was mature enough in 1932. Moreover, working on my arXiv I spent months to analyse a few dozens of algorithms to invert them - no one gives quadratic efficiency. Even if published in SIAM (in general N^3), or developed by authors which have monographs on special matrices (saying that it is possible to do in quadratic time, but surprisingly do not write how to do that, write only N^3 algorithm). The article on confluent Vandermonde matrix in wiki is still very poor. Even the definition was without source, I corrected it. But is was devised in 1901..

The <feasible> algorithms on FMM deserve to be promoted, if We want that the FMM topic will be ever applicable, not only the Strassen's.

Look deeper into my public activity, there are links to participation in science-policy parliamentary commission(*), advisory board at the government level, press agency news and opening plenary talks at reputable word conferences in Comp Sci/math. It is not typical, when scientists working in math and computer sci participates in public life, especially shaping EU science politics.

In close years also a few another english-written press agency news will appear.

I am planning to rework my wiki page since a few years, but I wait for apperance of my book, to include it as milestone in the popularization (do not confuse with science-popular texts) of FMM topic.

I am also in contact and consulation of my national reputable wiki editor, which advises me how to make my personal page professional, obeying wiki rules.

Besides, even if deleted I am sure that after another ~5 years my sole scientific results will justify the rebirth. However, I will not reveal my cards.

(*) British would name it "House of Representatives". Jerzy.Respondek (talk) 19:56, 18 December 2024 (UTC)

The personal page issue should be discussed at Wikipedia:Articles for deletion/Jerzy Respondek, not here. Note that Wikipedia is not for self-promotion (see e.g. WP:PROMOTION). And imo, a scientist should strive to advance science in the first place; in contrast, to become famous, the easiest way is to become a Hollywood actor. - Jochen Burghardt (talk) 13:46, 19 December 2024 (UTC)