## Iterative Form for Strassen Algorithm

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

### Iterative Form for Strassen Algorithm

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.

arzaqi

Posts: 27
Joined: Tue Nov 25, 2008 7:34 am UTC
Location: SE Asia

### Re: Iterative Form for Strassen Algorithm

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

Posts: 237
Joined: Sun Jul 04, 2010 8:40 pm UTC

### Re: Iterative Form for Strassen Algorithm

korona wrote: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.
EvanED

Posts: 3929
Joined: Mon Aug 07, 2006 6:28 am UTC

### Re: Iterative Form for Strassen Algorithm

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10209
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Who is online

Users browsing this forum: No registered users and 3 guests