如何将三角矩阵索引转换为行、列坐标?
How to convert triangular matrix indexes in to row, column coordinates?
我有这些索引:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,etc...
哪些是矩阵中节点的索引(包括对角线元素):
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
etc...
我需要从这些索引中获取 i,j
坐标:
1,1
2,1 2,2
3,1 3,2 3,3
4,1 4,2 4,3 4,4
5,1 5,2 5,3 5,4 5,5
6,1 6,2 6,3 6,4 6,5 6,6
etc...
当我需要计算坐标时,我只有一个索引,无法访问其他索引。
根本没有优化:
int j = idx;
int i = 1;
while(j > i) {
j -= i++;
}
优化:
int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5);
int j = idx - (i-1) * i / 2;
这里是演示:
您正在寻找这样的我:
sumRange(1, i-1) < idx && idx <= sumRange(1, i)
当 sumRange(min, max) 求和最小值和最大值之间的整数时,两者都包含在内。
但既然你知道 :
sumRange(1, i) = i * (i + 1) / 2
那么你有:
idx <= i * (i+1) / 2
=> 2 * idx <= i * (i+1)
=> 2 * idx <= i² + i + 1/4 - 1/4
=> 2 * idx + 1/4 <= (i + 1/2)²
=> sqrt(2 * idx + 1/4) - 1/2 <= i
在我的例子中(用标准 C 实现的 CUDA 内核),我使用从零开始的索引(并且我想排除对角线)所以我需要做一些调整:
// idx is still one-based
unsigned long int idx = blockIdx.x * blockDim.x + threadIdx.x + 1; // CUDA kernel launch parameters
// but the coordinates are now zero-based
unsigned long int x = ceil(sqrt((2.0 * idx) + 0.25) - 0.5);
unsigned long int y = idx - (x - 1) * x / 2 - 1;
这导致:
[0]: (1, 0)
[1]: (2, 0)
[2]: (2, 1)
[3]: (3, 0)
[4]: (3, 1)
[5]: (3, 2)
我也重新推导了Flórez-Rueda y Moreno 2001的公式,得出:
unsigned long int x = floor(sqrt(2.0 * pos + 0.25) + 0.5);
CUDA注:我想尽一切办法避免使用双精度数学,但CUDA中的单精度sqrt
函数根本不精确足以将大于 1.21 亿左右的位置转换为 x、y 坐标(当每个块使用 1,024 个线程并且仅沿 1 个块维度进行索引时)。一些文章采用了“修正”的方式将结果朝特定方向颠簸,但这不可避免地会在某一点上崩溃。
我有这些索引:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,etc...
哪些是矩阵中节点的索引(包括对角线元素):
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
etc...
我需要从这些索引中获取 i,j
坐标:
1,1
2,1 2,2
3,1 3,2 3,3
4,1 4,2 4,3 4,4
5,1 5,2 5,3 5,4 5,5
6,1 6,2 6,3 6,4 6,5 6,6
etc...
当我需要计算坐标时,我只有一个索引,无法访问其他索引。
根本没有优化:
int j = idx;
int i = 1;
while(j > i) {
j -= i++;
}
优化:
int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5);
int j = idx - (i-1) * i / 2;
这里是演示:
您正在寻找这样的我:
sumRange(1, i-1) < idx && idx <= sumRange(1, i)
当 sumRange(min, max) 求和最小值和最大值之间的整数时,两者都包含在内。 但既然你知道 :
sumRange(1, i) = i * (i + 1) / 2
那么你有:
idx <= i * (i+1) / 2
=> 2 * idx <= i * (i+1)
=> 2 * idx <= i² + i + 1/4 - 1/4
=> 2 * idx + 1/4 <= (i + 1/2)²
=> sqrt(2 * idx + 1/4) - 1/2 <= i
在我的例子中(用标准 C 实现的 CUDA 内核),我使用从零开始的索引(并且我想排除对角线)所以我需要做一些调整:
// idx is still one-based
unsigned long int idx = blockIdx.x * blockDim.x + threadIdx.x + 1; // CUDA kernel launch parameters
// but the coordinates are now zero-based
unsigned long int x = ceil(sqrt((2.0 * idx) + 0.25) - 0.5);
unsigned long int y = idx - (x - 1) * x / 2 - 1;
这导致:
[0]: (1, 0)
[1]: (2, 0)
[2]: (2, 1)
[3]: (3, 0)
[4]: (3, 1)
[5]: (3, 2)
我也重新推导了Flórez-Rueda y Moreno 2001的公式,得出:
unsigned long int x = floor(sqrt(2.0 * pos + 0.25) + 0.5);
CUDA注:我想尽一切办法避免使用双精度数学,但CUDA中的单精度sqrt
函数根本不精确足以将大于 1.21 亿左右的位置转换为 x、y 坐标(当每个块使用 1,024 个线程并且仅沿 1 个块维度进行索引时)。一些文章采用了“修正”的方式将结果朝特定方向颠簸,但这不可避免地会在某一点上崩溃。