Author |
Topic: transpose(A) * A for a sparse matrix (Read 724 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
 |
transpose(A) * A for a sparse matrix
« on: Jun 12th, 2009, 11:54pm » |
 Quote  Modify
|
I have a sparse matrix A which is of very large dimensions say (500000*25000).
I want to find, transpose(A) * A .
Space and Time are big constraints here, so try to minimize on them
|
| « Last Edit: Jun 13th, 2009, 1:50am by ic10503 » |
 IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #1 on: Jun 13th, 2009, 5:29am » |
Quote Modify
|
As far as i remember the definition of transpose all one has to do is to interchange the rows and columns.
Use a linked list to store the non-zero elements of the matrix.
struct linknode
{
int row;
int col;
int value;
struct linknode * next;
}
Once having stored al one has to do is traverse that list and for every node swap the row value with the column value.
Having done this you need one more traversal to display your list in the form of a matrix which is nothing but the transpose of the input.
NOTE: one can use a head node to store the dimensions and swap its row and column values as well ( in case you require ).
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #2 on: Jun 13th, 2009, 5:31am » |
Quote Modify
|
Sorry, i guess i did not read the ques properly i guess multiplication of a matrix by its transpose is what is asked.
and i have answered how to find the transpose.
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #3 on: Jun 13th, 2009, 5:39am » |
Quote Modify
|
Ok even if its so, i guess this should be pretty easy now. U have two linked lists one representing 'A' and the other its transpose. U need to multiply the "value" entities from the corresponding nodes of the two lists. All u need to do is make sure that you have to give preecedence to "row" entities (increasing order) and then to "column" entities (for same row values ).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #4 on: Jun 13th, 2009, 6:27am » |
Quote Modify
|
ATA composes rows of AT with columns of A, but the rows of AT are also the columns of A, so it will be much more efficient if your sparse matrix structure is stored column-wise rather than row-wise.
Then, rather than generating AT, just work from A directly. Take each pair of columns and sum products of matching elements while ignoring unmatched elements.
Also note that the result matrix will be symmetrical, so you can cut your work (almost) in half by only composing each unique pair of columns once.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #5 on: Jun 14th, 2009, 2:37am » |
Quote Modify
|
It would be interesting to have a quick way to check if two columns have any matching elements and avoid actually checking each pair of columns for a match, which involves scanning both column's lists of elements.
From the row-wise representation, we could first generate the pairs of columns that have matching element. It should help for very sparse matrices, but it is difficult to say if it is always improving things.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: transpose(A) * A for a sparse matrix
« Reply #6 on: Jun 15th, 2009, 11:59am » |
Quote Modify
|
Let me make a first try:
Start with empty matrix A, have a hashtable of used columns (initialy empty).
Make a hashtable of ATA addressed by it's coordinates.
Insert elements to A one each time.
If it is inserted to column not presented yet, the ATA is not affected. Start a list for the column in this case. Otherwise insert it into the list (list contains coordinate with pointer to the value).
Meanwhile make product of values on the list with the inserted value and increase/insert value in the correspording position of ATA.
It will take usually O(1) per entry on very sparse matrices. This takes sum of column size squared total time for entire algorithm.
BTW: May be the algorithm must be "transposed" ... I didn't actually think about it.
|
| « Last Edit: Jun 15th, 2009, 12:05pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print