Algorithm to beat Strassen’s Algorithm

by

You don’t really specify what the question is here, but I guess it is to disprove that this trivial algorithm runs faster than Strassen.

Say you divide your matrices into blocks each of dimension (n / k) X (n / k) (in your question, k is 4). Then each matrix will have k2 blocks, and there will be k3 block multiplications (each block in the first matrix will be multiplied by k blocks in the second matrix). Consequently, the complexity recurrence is

T(n) = k3 T(n / k) + Θ(n2).

By case 1 of the Master theorem, this implies

T(n) = Θ(nlogk(k3)) = Θ(n3).

This is the same as ordinary matrix multiplication. It does not beat Strassen, obviously.

More Related Contents:

  1. Calculate the sum with minimum usage of numbers
  2. Priority scoring algorithm [closed]
  3. How can I find the time complexity of an algorithm?
  4. Finding all cycles in a directed graph
  5. Peak signal detection in realtime timeseries data
  6. Least common multiple for 3 or more numbers
  7. Negative weights using Dijkstra’s Algorithm
  8. What’s the fastest algorithm for sorting a linked list?
  9. What algorithms compute directions from point A to point B on a map?
  10. Algorithm to generate a crossword [closed]
  11. Count number of 1’s in binary representation
  12. Check if one integer is an integer power of another
  13. Algorithm to tell if two arrays have identical members
  14. Quicksort vs heapsort
  15. Find 2 numbers in an unsorted array equal to a given sum
  16. Closest point to a given point
  17. Algorithm to find the most common substrings in a string
  18. What is amortized analysis of algorithms? [closed]
  19. Simplest way to get the top n elements of a Scala Iterable
  20. Find cycle of shortest length in a directed graph with positive weights
  21. Random points inside a parallelogram
  22. How is 2D bin packing achieved programmatically?
  23. Optimizing Conway’s ‘Game of Life’
  24. need an algorithm for collapsing netblock ranges into lists of superset ranges
  25. Convert light frequency to RGB?
  26. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  27. Bridges in a connected graph
  28. Breadth First Search and Depth First Search
  29. Portable efficient alternative to PDEP without using BMI2?
  30. Postfix notation to expression tree

Leave a Comment