My friends and I have to implement the Strassen algorithm in C, on a
RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
how to do that?
That's the final project of the "Parallel and Distributed Computing"
course, at UAEM, Mexico.
Our deadline is Feb. 14th, 2003.
If you can help us, please do it.
Thanks.
>My friends and I have to implement the Strassen algorithm in C, on a
>RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
>how to do that?
i suggest using an editor. if you run into problems once you have some
code then post your issue here, provided it's a c language issue, if you
have an algorithm question you'll need to post elsewhere (your class
materials presumably contain the necessary description).
--
bringing you boring signatures for 17 years
"Dr. K405" wrote:
>
> Hi.
>
> My friends and I have to implement the Strassen algorithm in C, on a
> RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
> how to do that?
>
> That's the final project of the "Parallel and Distributed Computing"
> course, at UAEM, Mexico.
>
How about doing a web search to figure out what the "Strassen algorithm"
actually does
googleing for it:
http://www.ii.uib.no/~fredrikm/fredrik/debug/strassen.html
seems to be a nice explanation. The whole algorithm doesn't
seem to be *that* complicated. A little bit recursion and
some arithmetic and you are done.
--
Karl Heinz Buchegger
kbuc...@gascad.at
> Hi.
>
> My friends and I have to implement the Strassen algorithm in C, on a
> RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
> how to do that?
Maybe you should have went to class.
-Daniel
>Hi.
>
>My friends and I have to implement the Strassen algorithm in C, on a
>RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
>how to do that?
Yes, but I won't get any grade for doing your work ;-)
So here's what you should do:
1. Get your books plus additional books on that algorithm from the
library (that huge building with lots of books inside).
2. Read all descriptions of the Strassen algorithm.
3. Get a pen and some paper
4. Think about how you would explain it to someone not knowing it.
5. Try to use it with a few small matrixes "by hand" (or pen&paper).
6. Think about how you worked #5 (schematic steps of your
calculations)
7. write results from #6 down in free language
8. rephrase notes from #7 as rules
9. rephrase rules in any given programming language you want to use
10. edit your source-code derived from #9, compile and test it until
your programs runs flawlessly
*SCNR*
>
>That's the final project of the "Parallel and Distributed Computing"
>course, at UAEM, Mexico.
>
>Our deadline is Feb. 14th, 2003.
Lots of time left to solve it yourself.
>
>If you can help us, please do it.
>
>Thanks.
So what *IS* your problem?
Don't you understand the algoritm itself? -> wrong news group
Don't you know how to code in C? -> get some books and learn
Have you completed your coding and experience any errors? post your
source here and someone will help
> Hi.
>
> My friends and I have to implement the Strassen algorithm in C, on a
I dont' know what Strassen is, but it's off topic on this newsgroup.
> RS6000 series Regatta running AIX v. 5.0 Do anyone have an idea of
> how to do that?
> That's the final project of the "Parallel and Distributed Computing"
You should probably look up the chapter on
MPI -"Message Passing Interface".
> course, at UAEM, Mexico.
>
> Our deadline is Feb. 14th, 2003.
>
> If you can help us, please do it.
>
Are you not a little late on this?
--
espen
Um, Daniel... Maybe you should have goed to English class...
PP
>>Maybe you should have went to class.
>>
>>-Daniel
>
> Um, Daniel... Maybe you should have goed to English class...
My English is actually quite good considering I was raised in a cardboard
box full of greased sloats and suffered considerable damage to my frontal
lobe due to a freak nun attack at the age of eleventeen.
-Daniel
> Um, Daniel... Maybe you should have goed to English class...
Um, Pika... need I even say it?
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Life without ostriches is like coffee with milk."
- Mika P. Nieminen
Not to mention the drinking problem ? :-)
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
Oh, I see. You're a Yorkshire man then?
PP
After you've graduated without learning anything other than how
to beg for help on homework problems on Usenet and get hired by
one of our esteemed manglers and assigned to our project which is
rapidly approaching deadline, you will be:
1) Hated.
2) Taunted.
3) The victim of numerous practical jokes.
4) Beat senseless when the boss isn't looking.
5) Fired for incompetence.
Not necessarily in the above order.
Say what, Joona? That I'm sweet?
PP
> Say what, Joona? That I'm sweet?
With a surname of Palasokeri you must be sweet, but what I was really
meaning was that you too should have gone to English class.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Nothing lasts forever - so why not destroy it now?"
- Quake
: Thanks.
Actually, this question is a good one for this newsgroup since the Strassen
matrix-product O(n^2.81) algorithm involves decomposing matrices, and it is
an interesting test of C's ability to manage such decomposition. I am hoping
for the OPs' sake that n is a power of 2, BTW.
Bloody Finns....
--GS
Not necessary to be a power of 2.
Here is a simple example (it's got some bugs but shows the idea):
#include<stdio.h>
#define BREAK 8
#define N 900
typedef union _matrix {
double **twobytwo; /* a pointer to an array, if size<=2 */
union _matrix **m_ptr; /* a half-dimension matrix */
} *matrix;
/* aliases to speed up code in callable functions */
#define a11 a->m_ptr[0]
#define a12 a->m_ptr[1]
#define a21 a->m_ptr[2]
#define a22 a->m_ptr[3]
#define b11 b->m_ptr[0]
#define b12 b->m_ptr[1]
#define b21 b->m_ptr[2]
#define b22 b->m_ptr[3]
#define c11 c->m_ptr[0]
#define c12 c->m_ptr[1]
#define c21 c->m_ptr[2]
#define c22 c->m_ptr[3]
#define d11 d->m_ptr[0]
#define d12 d->m_ptr[1]
#define d21 d->m_ptr[2]
#define d22 d->m_ptr[3]
void m_mul(int n, matrix a, matrix b, matrix c, matrix d);
void m_add(int n, matrix a, matrix b, matrix c);
void m_sub(int n, matrix a, matrix b, matrix c);
void s_mul(int n, matrix a, matrix c, double scalar);
void m_fill(int n, matrix a, double (*C)[N], int cr, int cc);
void m_dump(int n, matrix a, double (*C)[N], int cr, int cc);
void m_null(int n, matrix a);
matrix newmatrix(int n);
double DD[N][N],
EE[N][N],
*DDptr,
*EEptr;
main()
{
matrix a,
b,
c,
d;
int i2,
j2;
int n;
double s = 2.0;
/* matrix a,b,c,d; */
a = newmatrix(N);
b = newmatrix(N);
c = newmatrix(N);
d = newmatrix(N);
for (i2 = 0; i2 < N; i2++) {
for (j2 = 0; j2 < N; j2++) {
DD[i2][j2] = 0.5 * (double) (i2 + j2);
EE[i2][j2] = 0.0;
}
}
DDptr = ⅅ
EEptr = &EE;
m_fill(N, a, DDptr, 0, 0);
m_null(N, c);
m_null(N, d);
printf("done loading arrays\n");
m_mul(N, a, a, c, d);
m_dump(N, c, EEptr, 0, 0);
printf("\nDone multiplying\n");
}
void m_sub(int n, matrix a, matrix b, matrix c)
{
/* C=A-B */
int row,
col,
m;
if (n <= BREAK) {
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
*(*(c->twobytwo + row) + col) = *(*(a->twobytwo + row) +
col) - \
*(*(b->twobytwo + row) + col);
}
}
} else {
m = n / 2;
m_sub(m, a11, b11, c11);
m_sub(m, a12, b12, c12);
m_sub(m, a21, b21, c21);
m_sub(m, a22, b22, c22);
}
/* end of iterative subtraction routine */
}
void m_add(int n, matrix a, matrix b, matrix c)
{
/* C=A+B */
int row,
col,
m;
double **A = a->twobytwo;
double **B = b->twobytwo;
double **C = c->twobytwo;
if (n <= BREAK) {
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
*(*(C + row) + col) = *(*(A + row) + col) + *(*(B + row) +
col);
}
}
} else {
m = n / 2;
m_add(m, a11, b11, c11);
m_add(m, a12, b12, c12);
m_add(m, a21, b21, c21);
m_add(m, a22, b22, c22);
}
/* end of iterative addition routine */
}
void s_mul(int n, matrix a, matrix c, double scalar)
{
/* scalar multiplication c=scalar * a */
int row,
col,
m;
double **A = a->twobytwo;
double **C = c->twobytwo;
if (n <= BREAK) {
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
*(*(C + row) + col) = scalar * (*(*(A + row) + col));
}
}
} else {
m = n / 2;
s_mul(m, a11, c11, scalar);
s_mul(m, a12, c12, scalar);
s_mul(m, a21, c21, scalar);
s_mul(m, a22, c22, scalar);
}
/* end of iterative scalar multiplication routine */
}
void m_mul(int n, matrix a, matrix b, matrix c, matrix d)
{
/* C=A.B, and D is scratch or temporary space */
int row,
col,
l,
m;
double tmp,
number,
sum;
/* we exercise caution to take unit stride */
if (n <= BREAK) {
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
sum = 0.0;
for (l = 0; l < n; l++)
sum = sum + (a->twobytwo)[row][l] *
(b->twobytwo)[l][col];
(c->twobytwo)[row][col] = sum;
}
}
} else {
m = n / 2;
m_sub(m, a12, a22, d11);
m_add(m, b21, b22, d12);
m_mul(m, d11, d12, c11, d21);
m_sub(m, a21, a11, d11);
m_add(m, b11, b12, d12);
m_mul(m, d11, d12, c22, d21);
m_add(m, a11, a12, d11);
m_mul(m, d11, b22, c12, d12);
m_sub(m, c11, c12, c11);
m_sub(m, b21, b11, d11);
m_mul(m, a22, d11, c21, d12);
m_add(m, c21, c11, c11);
m_sub(m, b12, b22, d11);
m_mul(m, a11, d11, d12, d21);
m_add(m, d12, c12, c12);
m_add(m, d12, c22, c22);
m_add(m, a21, a22, d11);
m_mul(m, d11, b11, d12, d21);
m_add(m, d12, c21, c21);
m_sub(m, c22, d12, c22);
m_add(m, a11, a22, d11);
m_add(m, b11, b22, d12);
m_mul(m, d11, d12, d21, d22);
m_add(m, d21, c11, c11);
m_add(m, d21, c22, c22);
}
/* end of iterative multiply routine */
}
void m_fill(int n, matrix a, double (*C)[N], int cr, int cc)
{
/* routine to load ordinary array data into union _matrix */
int i,
j,
k,
m;
if (n <= BREAK) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
(a->twobytwo)[i][j] = C[i + cr][j + cc];
}
}
} else {
n /= 2;
m_fill(n, a11, C, cr, cc);
m_fill(n, a12, C, cr, cc + n);
m_fill(n, a21, C, cr + n, cc);
m_fill(n, a22, C, cr + n, cc + n);
}
}
void m_dump(int n, matrix a, double (*C)[N], int cr, int cc)
{
/* routine to load union _matrix data into ordinary array */
int i,
j,
k,
m;
if (n <= BREAK) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
C[i + cr][j + cc] = (a->twobytwo)[i][j];
}
}
} else {
n /= 2;
m_dump(n, a11, C, cr, cc);
m_dump(n, a12, C, cr, cc + n);
m_dump(n, a21, C, cr + n, cc);
m_dump(n, a22, C, cr + n, cc + n);
}
}
void m_null(int n, matrix a)
{
int i,
j,
k,
m;
if (n <= BREAK) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
(a->twobytwo)[i][j] = 0.0;
}
}
} else {
n /= 2;
m_null(n, a11);
m_null(n, a12);
m_null(n, a21);
m_null(n, a22);
}
}
matrix newmatrix(int n)
{
matrix a;
a = (matrix) malloc(sizeof(*a));
if (n <= BREAK) {
int i;
a->twobytwo = (double **) calloc(n, sizeof(double *));
for (i = 0; i < n; i++) {
a->twobytwo[i] = (double *) calloc(n, sizeof(double));
}
} else {
n /= 2;
a->m_ptr = (matrix *) calloc(4, sizeof(matrix));
a11 = newmatrix(n);
a12 = newmatrix(n);
a21 = newmatrix(n);
a22 = newmatrix(n);
}
return a;
}
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
He, he. I was attempting irony, but as everyone knows that is a difficult art.
In this case I must have failed miserably. At least with some readers. ;-)
PP
>In article <b1c2ho$8re$1...@oravannahka.helsinki.fi>, pal...@cc.helsinki.fi
>says...
>>
>>With a surname of Palasokeri you must be sweet,
I'd love to know the meaning of that !!
>but what I was really
>>meaning was that you too should have gone to English class.
>
>He, he. I was attempting irony, but as everyone knows that is a difficult art.
>In this case I must have failed miserably. At least with some readers. ;-)
Finns attempting irony in English, and misunderstanding each other.
Aint C great? :-)
> I'd love to know the meaning of that !!
Pala=bit, sokeri=sugar. Palasokeri=sugar that comes in bits.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Roses are red, violets are blue, I'm a schitzophrenic and so am I."
- Bob Wiley
[Singing to myself: "Sugar Bits" to the tune of
Al Hirt's "Sugar Lips"]
Thunks for the chackle.
:-)
-Mike
>Mark McIntyre <markmc...@spamcop.net> scribbled the following:
>> On 31 Jan 2003 17:14:09 -0600, in comp.lang.c , p...@hunaja.fi (Pika
>> Palasokeri) wrote:
>>>In article <b1c2ho$8re$1...@oravannahka.helsinki.fi>, pal...@cc.helsinki.fi
>>>says...
>>>>
>>>>With a surname of Palasokeri you must be sweet,
>
>> I'd love to know the meaning of that !!
>
>Pala=bit, sokeri=sugar. Palasokeri=sugar that comes in bits.
Excellent, and I picked up some semi-useful finnish into the bargain.
Sort of.
While in Sweden some Fins told me how to say "see the sea" and "see my
socks" (or something to the effect) in Finnish. AFAIR, not something to
say in Italy :)
--
GP_Spukgestalt, human C coder, killed by Don Barlone.
> While in Sweden some Fins told me how to say "see the sea" and "see my
> socks" (or something to the effect) in Finnish. AFAIR, not something to
> say in Italy :)
"Katso merta" is "look at the sea" in Finnish. In Italian it sounds
like "gazzo merda" which is something like "f*ck shit" AFAIK. "Look at
my socks" is "katso sukkiani" which would be, IIUC, "gazzo succhiani"
in Italian, but I haven't the faintest clue what that means.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"As we all know, the hardware for the PC is great, but the software sucks."
- Petro Tyschtschenko
> rv2...@hotmail.com (Dr. K405) writes:
>
>> Hi.
>>
>> My friends and I have to implement the Strassen algorithm in C, on a
>
> I dont' know what Strassen is, but it's off topic on this newsgroup.
Umm... so discussing algorithms that can be implemented in ANSI C is
off-topic?
>On Mon, 27 Jan 2003 21:22:01 +0100, Espen Myrland wrote:
>
>> rv2...@hotmail.com (Dr. K405) writes:
>>>
>>> My friends and I have to implement the Strassen algorithm in C, on a
>> I dont' know what Strassen is, but it's off topic on this newsgroup.
>Umm... so discussing algorithms that can be implemented in ANSI C is
>off-topic?
Yup. Discussing any algo is offtopic here.
OTOH you _could_ discuss how you implemented the algo, and ask for
tips on how to improve it. People round here do prefer you to try for
yourself first tho.
ps please trim your replies by removing any extraneous material below
your response. This saves bandwidth but more importantly it tells
people when they've reached the end of what you had to say.