A Statistical Adventure Towards Getting an Empirical O(n^2) Complexity in nxn matrix multiplication
by Soubhik Chakraborty and Kiran Kumar Sundararajan.
Abstract:
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.
Key Words:
Winograd's algorithm, empirical O(n^2) complexity
Authors:
Soubhik Chakraborty, soubhikc@yahoo.co.in
Kiran Kumar Sundararajani, kiranks@infotechsw.com
Editor:
Debasis Kundu,kundu@iitk.ac.in
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 268 times since July 24, 2006.
This article was revised on April 15, 2007.
Return to the 
Home Page.