在对称矩阵的线性索引 [英] Linear indexing in symmetric matrices

问题描述

我们可以使用线性索引，它遵循这一模式访问矩阵

We can access matrices using linear indexing, which follows this pattern

0 1 2

3 4 5

6 7 8

这很容易得到I，J坐标这种情况下（n为矩阵尺寸）。为0-指数化，这将是

It's easy to get the i,j coordinates for this case (n is the matrix dimension). For 0-index based, it would be.

我=指数/ N

J =指数％N

现在，如果我的基体是对称的，我只是想进入上部

Now, what if my matrix is symmetric and I only want to access the upper part

0 1 2 3

.. 4 5 6

..... 7 8

..... 7 8

........ 9

........ 9

我知道线性指标将由

指数= J + N *我 - 我（I-1）/ 2

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

但我想知道I，J给IDX。你们是否知道任何方式这样做的？我抬头一看这个位置，但我无法找到答案。先谢谢了。

but I want to know i,j given idx. Do you guys know of any way of doing this?. I looked up this here, but I couldn't find an answer. Thanks in advance.

推荐答案

如果你想使用您所使用的索引，你想避免你可以反函数的索引循环。我将使用k表示线性指标，以及所有指数都从零开始。正如你已经注意到

If you want to use the indexing that you used, and you want to avoid the loop you can invert the function for the indexing. I will use k to denote the linear index, and all indices are zero based. As you have noted

K = J + N * I - I *第（i-1）/ 2

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

看到，我们正在与正整数这里，而事实上，所有组合（I，J）映射到不同的k表示该函数是可逆的。其中我会做到这一点的方法是首先就是要注意

Seeing as we are working with positive integers here, and the fact that all combinations (i,j) map onto a distinct k means that the function is invertible. The way in which I would do this is to note first of all that

J =的k - N * 1 + I *（I-1）/ 2

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

这样，如果能找到哪个你上行，列被用上述公式定义。现在考虑你想要的行，它被定义为

such that if you can find the row which you are on, the column is defined by the above equation. Now consider you want the row, which is defined as

行=分钟{我|的k - 。妮+ I（I-1）/ 2> = 0}

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

如果你解决二次方程的k - 妮+ I（I-1）/ 2 = 0，走我的楼，这给你的行，即

If you solve the quadratic equation k - ni + i(i-1)/2 = 0 and take the floor of the i, this gives you the row, i.e.

行=地板（（2N​​ + 1 - 的sqrt（（2N + 1）^ 2 - 8k的））/ 2）

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

然后

J = K - 行* N +行*（行-1）/ 2

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

在伪code这将是

//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 ;

这消除了需要的循环，将大量的大型矩阵

This removes the need for the loop, and will be a lot quicker for large matrices

这篇关于在对称矩阵的线性索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！