A Statistical Adventure Towards Getting an Empirical O(n^2) Complexity in nxn matrix multiplication
by Soubhik Chakraborty and Kiran Kumar Sundararajan.
Given that the statistical approach "weighs" rather than counts the computing operations which arguably makes it more realistic(see Chakraborty et. al. Appl. Math. Lett. 13(5), 2000 and InterStat Dec2004), we revisit Winograd's algorithm statistically with the objective of getting an empirical O(n^2) complexity in two nxn matrix multiplication(n even). Next we briefly analyze our findings.
Winograd's algorithm, empirical O(n^2) complexity
Soubhik Chakraborty, firstname.lastname@example.org
Kiran Kumar Sundararajani, email@example.com
READING THE ARTICLE: You can read the article in
portable document (.pdf) format (198369 bytes.)
NOTE: The content of this article is the intellectual property of the authors, who retains all rights to future publication.
This page has been accessed 2452 times since July 24, 2006.
This article was revised on April 15, 2007.
Return to the Home Page.