Iterative Form for Strassen Algorithm

[arzaqi]

As we all already know, the Strassen algorithm for n by n matrix multiplication is written in recursive form. It has been proven (see: http://stackoverflow.com/questions/9317 ... -iteration for the detail) that any recursive algorithm can be transformed into its iterative form. But I never see the iterative form for Strassen algorithm. Does anyone know?

Once I know the iterative form of Strassen algorithm, I intend to prove its correctness using Hoare triples.

[korona]

You can use an explicit stack to transform any recursive algorithm to a iterative one.

[EvanED]

You can use an explicit stack to transform any recursive algorithm to a iterative one.

Right. It's not necessarily the case that there's what you might call a "natural" iterative algorithm, like there is for factorial or Fibonacci numbers.

[Yakk]

Create a bunch of stacks of matrices and a stack of operations. The operations include Strassen multiply, Create Submatrix, Add, Negate, Merge Submatrix, Clone, Pop, etc. Each operation specifies a matrix stack for each operation.

For each variable in the Strassen algorithm, have an individual stack. (This is easier than juggling stack depths)

The resulting algorithm ends up looking a lot like a recursive Strassen implementation, but instead you have a single loop that processes operations explicitly.