LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-15-2006, 06:03 AM   #1
George2
Member
 
Registered: Oct 2003
Posts: 354

Rep: Reputation: 30
an existing efficient matrix multiplication algorithm?


Hello everyone,


I am looking for an efficient way to implement matrix multiplication in C/C++. Are there any existing good ways?

The matrix is stored in an one-dimentional array.


thanks in advance,
George
 
Old 10-15-2006, 06:23 AM   #2
JonBrant
Member
 
Registered: Jul 2004
Distribution: Suse 10.2
Posts: 43

Rep: Reputation: 15
Square matrices or non square? It matters because if it only handles square matrices, it'll be much faster
 
Old 10-16-2006, 12:54 AM   #3
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
Hello.
If your matrix haven't any symmetry, then the multiplication
algorithm will be of O(N^2) complexity, i.e. multiplication
Code:
matrix(NxN)*vector(N)
takes about N*N operations (it is 10000 operations if N=100).

Now look at FFT (Fast Fourier Transform).
Ordinary Discrete Fourier transformation (DFT) of N-dim. vector f[n] is
Code:
F[k] = Sum( f[n]*exp(-2*pi*I/N*k*n) ,  n=0..N-1 ),
where I*I = -1
and may be rewritten as multiplication of some square matrix M and f[n].
On the other hand FFT uses the symmetry of M and can be computed in
O( N*log(N) ) operations. If N=100, then N*log(N) ~ 664 and it's about
10-15 times faster in this case than DFT (log(x) is base-2 logarithm).

So, if your matrix is symmetric, then there may be effective algorithm.
If not - multiply as always.

P.S.: One of my friends offer to use a video card for vector operations,
because most of them allows to do this!
P.P.S.: All this is related to matrix-matrix multiplication as well.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
USB drive, multiplication of mountpoints Jon_Roland Fedora 0 11-07-2005 10:18 PM
floating point multiplication irfanhab Programming 0 12-23-2004 10:13 PM
a more efficient set up dr_zayus69 Linux - Newbie 3 12-03-2004 09:47 AM
Parallel matrix multiplication abdobl Programming 3 09-22-2004 06:11 AM
Dual boot "merge" from existing 98 & existing Linux atsmith Linux - Newbie 4 07-13-2003 03:46 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 04:51 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration