线性指标上三角矩阵 [英] Linear index upper triangular matrix

问题描述

如果我有一个矩阵的上三角部分，上面的对角线偏移，存储为线性阵列，如何矩阵可以在（I，J）指数元件从阵列的线性索引提取

例如，线性阵列 [A0，A1，A2，A3，A4，A5，A6，A7，A8，A9 是矩阵存储器

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），对应的线性矩阵偏移数组中的索引，不递归。

有一个合适的结果， k2​​ij（INT K，INT N） - GT＆; （INT，INT）将满足，例如：

k2​​ij（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）
 [等等]


解决方案

方程从线性指标将（I，J）指数均

  I = N  -  2  - 楼（开方（-8 * K + 4 * N *（N-1）-7）/2.0  -  0.5）
J = K + I + 1  -  N *（N-1）/ 2 +（N-1）*（（N-1）-1）/ 2
 

逆操作，从（I，J）指数线性指数

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

验证与

 从numpy的进口triu_indices，开方
N = 10
对于在范围K（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-1）*（（N-1）-1）/ 2
    断言np.triu_indices（N，K = 1）[0] [K] ==我
    断言np.triu_indices（N，K = 1）[1] [k]的==Ĵ因为我在范围（N）：
    对于在范围Ĵ第（i + 1，n）的：
        K =（N *（N-1）/ 2） - （N-1）*（（N-1）-1）/ 2 + J  -  I  -  1
        断言triu_indices（N，K = 1）[0] [K] ==我
        断言triu_indices（N，K = 1）[1] [k]的==Ĵ
 

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?

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 And we want to know the (i,j) index in the array corresponding to an offset in the linear matrix, without recursion.

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]

解决方案

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

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

Verify 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屋！