Numerical Recipes Forum  

Go Back   Numerical Recipes Forum > Obsolete Editions Forum > General Computing and Open Discussions

Reply
 
Thread Tools Display Modes
  #1  
Old 11-21-2005, 06:38 AM
sertackoksal sertackoksal is offline
Registered User
 
Join Date: Nov 2005
Posts: 2
Exclamation large matrix calculation

Hello,

I use MATLAB for computing and I have to handle the matrices in the order of thousands. I try to do my computations using full matrices but the program can not solve, the inversion for example. So that I need an algorithm that enables to calculate only one value of a large matrix, for example (3,5) of a (2000X2000) matrix. The calculations include both +,-,*,inverse,/,\.

Can anyone have ever dealed with such large matrices.

Thank you.

Sertaç
Reply With Quote
  #2  
Old 11-21-2005, 03:36 PM
gaspari gaspari is offline
Registered User
 
Join Date: Aug 2004
Posts: 14
Dear Sertac, you wrote

>I use MATLAB for computing and I have to handle the matrices in the order of >thousands. I try to do my computations using full matrices but the program can not >solve, the inversion for example. So that I need an algorithm that enables to calculate >only one value of a large matrix, for example (3,5) of a (2000X2000) matrix. The >calculations include both +,-,*,inverse,/,\.
>
>Can anyone have ever dealed with such large matrices.
>
>Thank you.

It is hard to believe that you really need so large dense matrices. And it is hard to believe that you really need to compute the inverse of so large matrices.

Basically dense matrices larger than...say 100x100 are difficult to "manage". Increasing the matrix dimension the time required to compute the inverse will be not acceptable,
the roundoff error becomes important and with large n the memory required to
store the matrix will be not available.

For example solving Ax=b (liner system) requires O(n**3) floating point multiplication and O(n**2) memory locations. In addition to solve that system the inverse matrix is not required, at all.


Basically large matrices are sparse, i.e. a lot of element are equal to zero or very close to zero. In that case there are more intelligent algorithms and storage schemes.
Using the sparse property you can try to use only O(n) operation and memory locations .

Unfortunately the product of two sparse matrices (with a small sparsity coefficient) can be not sparse (i.e. the final matrix is dense).

Which is your problem? Homework? Just curiosity?

In most cases large matrices are used in discretization of partial differential equations, I don't think you are working on that problem. Usually people working on numerical PDE solution know very well the issue.

My final, humble, suggestion is to study some NA textbook book You can start with NR (chapter 2) reading the material about sparse linear system.

Hope this helps

Max
Reply With Quote
  #3  
Old 11-22-2005, 02:41 AM
sertackoksal sertackoksal is offline
Registered User
 
Join Date: Nov 2005
Posts: 2
Dear Max,

I need to calculate in MATLAB
sert=1;
for ww=0:0.1:100
fun=MStiffness-ww^2*MMass;
burc=(Stiffness-ww^2*Mass+i*ww*Damping)\I;
alpha=(I+burc*fun)\burc;
oto(sert)=burc(r1,r2);
bus(sert)=alpha(r1,r2);
sert=sert+1;
end

Stiffness, Mass, Damping, MMass and MStiffness are all large matrices stored as sparse matrices but I need only one of the element of resultant matrix. By the way I is identity matrix.

This is about my thesis, structural modification.

I could not find a solution for a long time.

Thank you.

Sertaç
Reply With Quote
  #4  
Old 01-21-2009, 05:16 AM
kutta kutta is offline
Registered User
 
Join Date: Nov 2002
Location: India
Posts: 101
MatrixMultiplicationOrderProblem

Quote:
Originally Posted by sertackoksal View Post
Hello,

I use MATLAB for computing and I have to handle the matrices in the order of thousands. I try to do my computations using full matrices but the program can not solve, the inversion for example. So that I need an algorithm that enables to calculate only one value of a large matrix, for example (3,5) of a (2000X2000) matrix. The calculations include both +,-,*,inverse,/,\.

Can anyone have ever dealed with such large matrices.

Thank you.

Sertaç

Hello Comrade

In order to detrmine the best order in which to to carry out matrix multiplication algorithm.we use ordinary algorithmThus
to multiply p*q matrix & q*r matrix we do pqr elementwise multiplication
There are two observations to be made.
one we get the same rresult no matter in which order the multiplications are done,since it is associative:ie
A(BC)=(AB)C
Second the order can make a big difference in the amount of work done(ie its cost)
Contextualy the following algorithm I tried in C++ may please be reviewed for the concept comprehension.
Quote:

#include <iostream>
#include <algorithm>
#include <functional>
#include <stdio.h>

#include <conio.h>
#include <fstream>
#include <string>
#include <vector>

#include <string>
#include <conio.h>
#include <time.h>
#include <cctype>
#include <limits>
#include <iomanip.h>
#include <utility>
#include <functional>
#include <memory>
#include <stdio.h>



using namespace std;

float matrixOrder(int[] dim,int n,int[] multOrder);

float matrixOrder(int[] dim,int n,int[] multOrder){

int low,high,k,bestlast,last;
float bestcost,cost,a,b,c,multcost,extractOrderWrap;
int[][] last = new int[n+1][n+1];
float[][] cost = new float[n+1][n+1];
int n,dim,multOrder;
float leftD,midD,rightD,,
for(low = n-1;low >= n ; low--)
for(high =n+1; high <= n; high++)
if (high-low ==1)
bestcost = 0;
bestlast = -1;
else
bestcost = 0;
for(k =low+1; k <= high-1;k++)
a = cost[low][k];
b = cost[k][high];
c = multcost(dim.[low],dim.[k],dim.[high]);
if(a+b+c < bestcost);
bestcost = a+b+c;
bestlast = k;
cost[low][high]=bestcost;
last[low][high]=bestlast;

// extractOrderWrap(n,last,multOrder);
return [0][n];

float multCost(float leftD,float midD,float rightD);
return leftD* midD *rightD;
}
int main()
{
return 0;
}

Thanking you
As
Kutta(C.R.Muthukumar)










Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


All times are GMT -5. The time now is 12:29 PM.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.