From: "Wiljan Derks" <Wiljan.Derks@zonnet.nl>
Subject: Re: GNAT compiler switches and optimization
Date: Tue, 24 Oct 2006 21:21:13 +0200
Date: 2006-10-24T21:21:13+02:00 [thread overview]
Message-ID: <453e675e$0$30736$bf4948fe@news.tele2.nl> (raw)
In-Reply-To: pan.2006.10.24.09.54.07.340442@linuxchip.demon.co.uk.uk.uk
"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:pan.2006.10.24.09.54.07.340442@linuxchip.demon.co.uk.uk.uk...
> I know you're quite correct that there is a faster algorithm for
> large n. But looking at the loops, I don't see where the same
> number pairs are multiplied at different points in the calculation.
> Doesn't A(1,1)*B(1,1) only appear in C(1,1)? Where else?
>
> Aren't they only the same additions if the same products are summed?
>
Sorry, I was to fast writing this remark.
Since I was wrong, I checked my old school papers and found how to perfrom a
faster matrix multiplication.
It is called the Strassen algorithm.
For more details see: http://en.wikipedia.org/wiki/Strassen_algorithm
It still looks to me, there may be considerable savings since this algortihm
is O(n^2.8) instead of O(n^3).
Wikipedia also mention the drawback: numeric instability!
So the subtraction and addition tricks probably lead to less accurate
results in certain cases.
next prev parent reply other threads:[~2006-10-24 19:21 UTC|newest]
Thread overview: 68+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-10-20 10:47 GNAT compiler switches and optimization tkrauss
2006-10-20 11:04 ` Duncan Sands
2006-10-21 10:45 ` Stephen Leake
2006-10-20 11:42 ` Duncan Sands
2006-10-20 15:41 ` Martin Krischik
2006-10-20 12:09 ` Samuel Tardieu
2006-10-20 12:18 ` Samuel Tardieu
2006-10-20 12:12 ` Gautier
2006-10-20 12:35 ` Dmitry A. Kazakov
2006-10-20 15:53 ` Martin Krischik
2006-10-20 12:52 ` Gautier
2006-10-20 13:27 ` claude.simon
2006-10-20 15:38 ` Robert A Duff
2006-10-20 19:32 ` Gautier
2006-10-20 15:56 ` Jeffrey Creem
2006-10-20 16:30 ` Martin Krischik
2006-10-20 19:51 ` Gautier
2006-10-20 22:11 ` Jeffrey R. Carter
2006-10-20 23:52 ` Jeffrey Creem
2006-10-21 7:37 ` Gautier
2006-10-21 16:35 ` Jeffrey Creem
2006-10-21 17:04 ` Pascal Obry
2006-10-21 21:22 ` Jeffrey Creem
2006-10-22 3:03 ` Jeffrey Creem
2006-10-22 7:39 ` Jeffrey R. Carter
2006-10-22 11:48 ` tkrauss
2006-10-22 18:02 ` Georg Bauhaus
2006-10-22 18:24 ` Jeffrey Creem
2006-10-23 0:10 ` Georg Bauhaus
2006-10-22 20:20 ` Jeffrey R. Carter
2006-10-22 12:31 ` Gautier
2006-10-22 20:26 ` Jeffrey R. Carter
2006-10-22 21:22 ` Gautier
2006-10-22 18:01 ` tmoran
2006-10-22 20:54 ` Jeffrey R. Carter
2006-10-22 13:50 ` Alinabi
2006-10-22 15:41 ` Jeffrey Creem
2006-10-23 0:02 ` Alinabi
2006-10-23 5:28 ` Gautier
2006-10-23 16:32 ` Alinabi
2006-10-22 15:57 ` Jeffrey Creem
2006-10-22 19:32 ` Damien Carbonne
2006-10-22 20:00 ` Gautier
2006-10-22 20:51 ` Damien Carbonne
2006-10-23 2:15 ` Jeffrey Creem
2006-10-23 2:29 ` Jeffrey R. Carter
2006-10-23 1:31 ` Jeffrey Creem
2006-10-23 3:10 ` Jeffrey Creem
2006-10-23 7:31 ` Jeffrey R. Carter
2006-10-23 11:55 ` Jeffrey Creem
2006-10-23 19:52 ` Wiljan Derks
2006-10-23 20:25 ` Jeffrey R. Carter
2006-10-24 9:52 ` Dr. Adrian Wrigley
2006-10-24 11:50 ` Jeffrey Creem
2006-10-24 16:24 ` Jeffrey R. Carter
2006-10-25 3:50 ` Jeffrey Creem
2006-10-25 15:32 ` claude.simon
2006-10-24 19:21 ` Wiljan Derks [this message]
2006-10-23 12:33 ` Warner BRUNS
2006-10-23 12:40 ` Warner BRUNS
2006-10-23 13:52 ` Georg Bauhaus
2006-10-23 17:11 ` Warner BRUNS
2006-10-23 17:57 ` Dr. Adrian Wrigley
2006-10-23 15:02 ` Robert A Duff
2006-10-23 20:22 ` Jeffrey R. Carter
2006-10-21 18:28 ` tmoran
2006-10-23 6:28 ` Martin Krischik
2006-10-21 12:39 ` Dr. Adrian Wrigley
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox