线性索引上三角矩阵 [英] Linear index upper triangular matrix

问题描述

如果我有矩阵的上三角部分，在对角线上偏移，存储为线性数组，如何从线性数组中提取矩阵元素的 (i,j) 索引数组的索引?

If I have the upper triangular portion of a matrix, offset above the diagonal, stored as a linear array, how can the (i,j) indices of a matrix element be extracted from the linear index of the array?

例如线性数组[a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 就是矩阵的存储

For example, the linear array [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 is storage for the matrix

0  a0  a1  a2  a3
0   0  a4  a5  a6
0   0   0  a7  a8
0   0   0   0  a9
0   0   0   0   0

而且我们想知道与线性矩阵中的偏移量相对应的数组中的 (i,j) 索引，无需递归.

And we want to know the (i,j) index in the array corresponding to an offset in the linear matrix, without recursion.

一个合适的结果，k2ij(int k, int n) ->(int, int) 将满足，例如

A suitable result, k2ij(int k, int n) -> (int, int) would satisfy, for example

k2ij(k=0, n=5) = (0, 1)
k2ij(k=1, n=5) = (0, 2)
k2ij(k=2, n=5) = (0, 3)
k2ij(k=3, n=5) = (0, 4)
k2ij(k=4, n=5) = (1, 2)
k2ij(k=5, n=5) = (1, 3)
 [etc]

推荐答案

从线性索引到(i,j)索引的方程是

The equations going from linear index to (i,j) index are

i = n - 2 - floor(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5)
j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2

逆运算，从(i,j)索引到线性索引是

The inverse operation, from (i,j) index to linear index is

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

在 Python 中验证:

Verify in Python with:

from numpy import triu_indices, sqrt
n = 10
for k in range(n*(n-1)/2):
    i = n - 2 - int(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5)
    j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2
    assert np.triu_indices(n, k=1)[0][k] == i
    assert np.triu_indices(n, k=1)[1][k] == j

for i in range(n):
    for j in range(i+1, n):
        k = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1
        assert triu_indices(n, k=1)[0][k] == i
        assert triu_indices(n, k=1)[1][k] == j

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