Latest LQ Deal: Latest LQ Deals
 LinuxQuestions.org an existing efficient matrix multiplication algorithm?
 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.

 10-15-2006, 06:03 AM #1 George2 Member   Registered: Oct 2003 Posts: 354 Rep: 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
 10-15-2006, 06:23 AM #2 JonBrant Member   Registered: Jul 2004 Distribution: Suse 10.2 Posts: 43 Rep: Square matrices or non square? It matters because if it only handles square matrices, it'll be much faster
 10-16-2006, 12:54 AM #3 firstfire Member   Registered: Mar 2006 Location: Ekaterinburg, Russia Distribution: Debian, Ubuntu Posts: 709 Rep: 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.

 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 Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Jon_Roland Fedora 0 11-07-2005 10:18 PM irfanhab Programming 0 12-23-2004 10:13 PM dr_zayus69 Linux - Newbie 3 12-03-2004 09:47 AM abdobl Programming 3 09-22-2004 06:11 AM atsmith Linux - Newbie 4 07-13-2003 03:46 PM

LinuxQuestions.org

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

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -