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

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 2254 times since July 24, 2006.

This article was revised on April 15, 2007.

Return to the InterStat Home Page.