Re: Triangular Matrix
- From: Eric Sosman <Eric.Sosman@xxxxxxx>
- Date: Mon, 30 Oct 2006 18:40:37 -0500
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.
--
Eric.Sosman@xxxxxxx
.
- References:
- Triangular Matrix
- From: Je-Givara
- Triangular Matrix
- Prev by Date: Re: Triangular Matrix
- Next by Date: Re: Out-of-bounds Restrictions?
- Previous by thread: Re: Triangular Matrix
- Next by thread: not writing to file
- Index(es):
Relevant Pages
|
|
