Winograd’s algorithm statistically revisited: It pays to weigh than to count!

摘要

Given that the statistical approach “weighs” rather than counts the computing operations which arguably makes it more realistic (see [Soubhik Chakraborty, Pabitra Pal Choudhury, A statistical analysis of an algorithm’s complexity, Applied Mathematics Letters 13 (5) (2000); Soubhik Chakraborty et al., On how statistics provides a reliable and valid measure for an algorithm’s complexity, InterStat Dec2004#2 (http://interstat.statjournals.net/)]), we revisit Winograd’s algorithm statistically with the objective of getting an empirical O(n2) complexity in two n × n matrix multiplication (n even). Next we briefly analyze our findings.