c++ - 如何使通过矩阵的上三角的环变平？

我遇到的情况是，我将openMP用于Xeon Phi协处理器，并且有机会并行处理“令人尴尬的并行” double for循环。

但是，for循环遍历上三角（包括对角线）：

for (int i = 0; i < n; i++)
     // access some arrays with the value of i
     for (int j = i; j < n; j++)
         // do some stuff with the values of j and i

所以，我有了循环的总大小，

for (int q = 0; q < ((n*n - n)/2)+n; q++)
    // Do stuff

但是我在努力的地方是：

如何从q计算i和j？可能吗？



同时，我只是在做一个完整的矩阵，从那里计算i和j，并且仅当j> = i ...时才做我的事情，但这仍然留下了大量的线程开销。

最佳答案

如果我重申您的问题，要从i查找j和q，则需要最大的i

    q >= i*n - (i-1)*i/2

定义j为

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

如果您拥有如此出色的i，那么

    (i+1)*n - i*(i+1)/2 > q                             >= i*n - (i-1)*i/2
     n-i                > (q - i*n - (i-1)*i/2)         >= 0
     n                  > j = i + (q - i*n - (i-1)*i/2) >= i

这是找到i的第一种迭代方法：

    for (i = 0; q >= i*n - (i-1)*i/2; ++i);
    i = i-1;

如果对q进行迭代，则i的计算很可能会利用迭代过程。

第二种方法可以使用sqrt

    i*n - i²/2 + i/2 ~ q
    i²/2 - i(n+1/2) + q ~ 0
    delta = (n+0.5)² - 2q
    i ~ (n+0.5) - sqrt(delta)

i可以定义为floor((n+0.5) - sqrt((n+0.5)² - 2q))

关于c++ - 如何使通过矩阵的上三角的环变平？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39944731/