Prev: Ada Leaking Into Day Job
Next: Ada Lovelace Day on march 24th
From: Ole-Hjalmar Kristensen on 22 Mar 2010 04:56
jonathan <johnscpg(a)googlemail.com> writes:

<snip>
> It's the heart of the matter, and it is just getting worse. Helps
> convince me
> anyway that I did not waste time on an unimportant matter! In
> numerical linear
> algebra the usual solution is to restructure matrices as a collection
> of
> blocks. That has a few of its own problems though. Minor footnote: I
> did

Another approach is to keep the matrix as a single big matrix, but
reformulate your loops as recursive procedure which divides the matrix
a number of times and then loops at the lowest level. The increased
efficiency from tha cache will typically more than outweigh the
overhead from the recursion.

The following is a java version of the idea applied to transposing a
lagre matrix. (I have Ada and C versions as well) The recursive
version is typically about ten times faster than the pure nested loop
version. It is also interesting to see the speed of tha java version
relative to a C or Ada version. Try it and see...


import java.util.*;

class transpose
{
private static final int u1 = 6000;
private static final int u2 = 6000;
private static int[][] a = new int[u1][u2];
private static int[][] b = new int[u1][u2];

private static void init(int[][]x)
{
int i = 0;
int j = 0;
for (i = 0; i < x.length; i++) {
for (j = 0; j < x[i].length; j++) {
x[i][j] = i;
}
}
}

private static void loop_transpose(int[][]a, int[][]b, int ll1, int ul1, int ll2, int ul2)
{
int i = 0;
int j = 0;
for (i = ll1; i <= ul1; i++) {
for (j = ll2; j <= ul2; j++) {
b[j][i] = a[i][j];
}
}
}

private static void recursive_transpose(int[][]a, int[][]b, int ll1, int ul1, int ll2, int ul2, int cutoff)
{
int split = 0;
if (ul1 - ll1 > cutoff || ul2 - ll2 > cutoff) {
if (ul1 - ll1 > ul2 - ll2 ) {
split = (ul1 - ll1)/2;
recursive_transpose(a,b,ll1,ll1+split,ll2,ul2,cutoff);
recursive_transpose(a,b,ll1+1+split,ul1,ll2,ul2,cutoff);
}else{
split = (ul2 - ll2)/2;
recursive_transpose(a,b,ll1,ul1,ll2,ll2+split,cutoff);
recursive_transpose(a,b,ll1,ul1,ll2+1+split,ul2,cutoff);
}
}else {
loop_transpose(a,b,ll1,ul1,ll2,ul2);
}
}

public static void main(String[] args)
{
init(a); init(b);

long start = (new Date()).getTime();
loop_transpose(a,b,0,u1-1,0,u2-1);

long stop = (new Date()).getTime();
System.out.println( "loop " + (stop-start));

start = (new Date()).getTime();
recursive_transpose(a,b,0,u1-1,0,u2-1,16);

stop = (new Date()).getTime();
System.out.println( "recursive " + (stop-start));
}
}

--
C++: The power, elegance and simplicity of a hand grenade.
 | 
Pages: 1
Prev: Ada Leaking Into Day Job
Next: Ada Lovelace Day on march 24th