Re: Triangular Matrix
- From: Simon Biber <news@xxxxxxxxx>
- Date: Tue, 31 Oct 2006 10:26:40 +1100
Je-Givara wrote:
I want to get a Mapping Function for following sparse matrix of size
NxN , where N is odd
-----------------------------------------------------------------------------------
0 0 0 0 0 ... 0 a1,n
0 0 0 0 0 ... ... 0 0
0 0 0 0 0 ... a3,n-2 a3,n-1 a3,n
0 0 0 0 0 .. ... 0 0
0 0 0 ... a5,n-4 a5,n-3 a5,n-2 a5,n-1 a5,n
.... .... ... ... ... ... .. ...
.......................................................................
.......................................................................
0 0 0 0 0 ..... 0 0 0
an1 an2 an3 an4 an5 ... an,n-2 an,n-1 an,n
-------------------------------------------------------------------------------------
Suggest a mapping function to map the elements of the matrix onto a
single dimensional array
in which zero "0" elements do not have representation.
Please, any body could find mapping function formula for this kind of
Matrix.
Take a coordinate within the matrix as (x, y) where 0 <= x,y < N. We want to find an index value for a flat array that skips over elements that are known to be zero.
I noted that from the y coordinate you can calculate the number of real values that have gone before as a sum. I started with the formula
Sum[k, {k, 1, n}] == n * (n + 1) / 2
Noting that only odd rows are significant, y is divided by 2. Some fiddling with constants by trial and error and I have a formula.
#include <stdio.h>
#include <assert.h>
#define N 7
#define INDEX(x, y) (((y)/2 + 2) * ((y)/2 + 3) / 2 - N - 2 + (x))
#define ARRSIZE ((N/2 + 2) * (N/2 + 3) / 2 - 2)
int main(void)
{
int arr[ARRSIZE];
int x, y;
assert(N % 2 == 1 /* odd N */);
printf("arr[%d]\n", ARRSIZE);
for(y = 0; y < N; y += 2)
{
for(x = N - y - 1; x < N; x++)
{
printf("(%d, %d) -> %d\n", x, y, INDEX(x, y));
}
}
return 0;
}
C:\docs\prog\c>gcc sparse.c && a
arr[13]
(6, 0) -> 0
(4, 2) -> 1
(5, 2) -> 2
(6, 2) -> 3
(2, 4) -> 3
(3, 4) -> 4
(4, 4) -> 5
(5, 4) -> 6
(6, 4) -> 7
(0, 6) -> 6
(1, 6) -> 7
(2, 6) -> 8
(3, 6) -> 9
(4, 6) -> 10
(5, 6) -> 11
(6, 6) -> 12
The index values go from 0 of course, since this is C.
--
Simon.
.
- References:
- Triangular Matrix
- From: Je-Givara
- Triangular Matrix
- Prev by Date: Re: C Interview Questions
- Next by Date: Re: Triangular Matrix
- Previous by thread: Triangular Matrix
- Next by thread: Re: Triangular Matrix
- Index(es):
Relevant Pages
|
|
