Triangular Matrix

[Je-Givara]

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.

 

[Simon Biber]

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.

 

[Eric Sosman]

Je-Givara wrote On 10/30/06 15:41,:

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.

You've numbered the rows and columns starting from one
rather than C's usual zero, but that's all right: I'll use
that numbering (but wanted to draw attention to it to avoid
possible confusion). In those terms, it looks like each
odd-numbered row R has N-R zeroes followed by R possible
non-zeroes, and each even-numbered row is zero throughout.
(If that's not what your diagram means, ignore the rest.)

To access column C of row R, then, you first test for
R odd and C > N-R: if either test fails, you return a zero
(on a fetch) or announce a programming error (on a store).
You might also check for 1 <= R,C <= N and announce an error
if either is out of bounds; it depends on how trustworthy you
consider the source of R's and C's. In what follows, I'll
assume R and C are in range, with R odd and C > N-R.

How many non-zeroes are in the rows before row R? There
are 1 + 3 + ... + (R-2) = (R-1)*(R-1)/4. How many non-zeroes
are in row R before column C? The row's first non-zero is
in column N-R+1, so there are C-(N-R+1) = R+C-N-1 prior to
column C. Add these to find the number of non-zeroes that
appear before row R column C, and you get

(R-1)*(R-1)/4 + R+C-N-1 = (R+1)*(R+1)/4 + C - N - 1

Double-check by computing a few sample values. The
top right corner is at R=1,C=N, and the formula says it goes
at index 0. Good so far. In row R=3, the three non-zeroes
are at C=N-2,N-1,N, and the formula gives 1,2,3. Looks good.

How big must the linear array be? Easy: figure out the
index of the bottom right corner at R=N,C=N -- and then
recall that C arrays are zero-based, so the number of elements
is one larger than the greatest index.

Going the other way (from a linear array index I to the
corresponding R,C pair) is left as an exercise.

 

[Je-Givara]

Je-Givara wrote On 10/30/06 15:41,:

You've numbered the rows and columns starting from one
rather than C's usual zero, but that's all right: I'll use
that numbering (but wanted to draw attention to it to avoid
possible confusion). In those terms, it looks like each
odd-numbered row R has N-R zeroes followed by R possible
non-zeroes, and each even-numbered row is zero throughout.
(If that's not what your diagram means, ignore the rest.)

To access column C of row R, then, you first test for
R odd and C > N-R: if either test fails, you return a zero
(on a fetch) or announce a programming error (on a store).
You might also check for 1 <= R,C <= N and announce an error
if either is out of bounds; it depends on how trustworthy you
consider the source of R's and C's. In what follows, I'll
assume R and C are in range, with R odd and C > N-R.

How many non-zeroes are in the rows before row R? There
are 1 + 3 + ... + (R-2) = (R-1)*(R-1)/4. How many non-zeroes
are in row R before column C? The row's first non-zero is
in column N-R+1, so there are C-(N-R+1) = R+C-N-1 prior to
column C. Add these to find the number of non-zeroes that
appear before row R column C, and you get

(R-1)*(R-1)/4 + R+C-N-1 = (R+1)*(R+1)/4 + C - N - 1

Double-check by computing a few sample values. The
top right corner is at R=1,C=N, and the formula says it goes
at index 0. Good so far. In row R=3, the three non-zeroes
are at C=N-2,N-1,N, and the formula gives 1,2,3. Looks good.

How big must the linear array be? Easy: figure out the
index of the bottom right corner at R=N,C=N -- and then
recall that C arrays are zero-based, so the number of elements
is one larger than the greatest index.

Going the other way (from a linear array index I to the
corresponding R,C pair) is left as an exercise.

unfortunatly this is not RIGHT

 

[Eric Sosman]

Je-Givara wrote On 11/02/06 09:00,:

unfortunatly this is not RIGHT

I never claimed to be infallible. Would you mind
revealing my error, so I can learn and improve myself?

 

[linuxlong]

Je-Givara wrote On 11/02/06 09:00,:

I never claimed to be infallible. Would you mind
revealing my error, so I can learn and improve myself?