对称矩阵中的线性索引

Question

我们可以使用线性索引访问矩阵,该索引遵循此模式

0 1 2

3 4 5

6 7 8

在这种情况下很容易得到i,j坐标(n是矩阵维度).对于0指数,它将是.

i = index/n

j =指数%n

现在,如果我的矩阵是对称的,我只想访问上半部分

0 1 2 3

.. 4 5 6

..... 7 8

........ 9

我知道线性指数将由.给出

index = j + n*i - i(i-1)/ 2

但我想知道我,j给出了idx.你们知道这样做的任何方式吗？我在这里查了一下,但我找不到答案.提前致谢.

Answer 1

如果要使用所使用的索引,并且希望避免循环,则可以反转索引功能.我将使用k来表示线性索引,并且所有索引都是基于零的.如你所知

k = j + n*i - i*(i-1)/ 2.

看到我们正在使用正整数,并且所有组合(i,j)映射到不同的k意味着该函数是可逆的.我这样做的方式首先要注意这一点

j = k-n*i + i*(i-1)/ 2

这样,如果您可以找到您所在的行,则该列由上面的等式定义.现在考虑你想要的行,定义为

row = min {i | k-ni + i(i-1)/ 2> = 0}.

如果求解二次方程k - ni + i(i-1)/ 2 = 0并取i的最低点,则会给出行,即

row = floor((2n + 1 - sqrt((2n + 1)^ 2 - 8k))/ 2)

然后

j = k - row*n + row*(row-1)/ 2.

在伪代码中,这将是

//Given linear index k, and n the size of nxn matrix
i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;
j = k - n*i + i*(i-1)/2 ;

这消除了对循环的需要,并且对于大型矩阵来说会更快

Answer 2

循环遍历行，跟踪每行的偏移量以及每行的起始索引：

offset = 0;
startOfRow = 0;
for(i=0;i<height;i++){
    endOfRow = startOfRow + (width - offset);
    if(idx < endOfRow){ 
        j = (idx - endOfRow) + width;
        return {i,j};
    } else {                           
        startOfRow = endOfRow;
        offset++;
    }
}

我不懂Matlab，所以它只是伪代码，但它应该可以工作。正如霍克勒所说，确保你的索引是正确的。我i,j在这里使用的就像你在示例中使用的那样，但对我来说感觉很奇怪。