如何将对角矩阵沿一条轴分成相等数量的项? [英] How to split diagonal matrix into equal number of items each along one of axis?

问题描述

我有一个非常大的对角矩阵，需要将其拆分以进行并行计算.由于数据局部性的问题，没有必要遍历矩阵并在 n 个线程之间划分每个第 n 个计算.目前，我正在按以下方式对 k x k 对角矩阵进行划分，但它在计算数量方面产生了不相等的分区(最小的部分计算的时间比计算时间长几倍).最大).

I have a very large diagonal matrix that I need to split for parallel computation. Due to data locality issues it makes no sense to iterate through the matrix and split every n-th calculation between n threads. Currently, I am dividing k x k diagonal matrix in the following way but it yields unequal partitions in terms of the number of the calculations (smallest piece calculates a few times longer than the largest).

def split_matrix(k, n):
    split_points = [round(i * k / n) for i in range(n + 1)] 
    split_ranges = [(split_points[i], split_points[i + 1],) for i in range(len(split_points) - 1)]
    return split_ranges

import numpy as np
k = 100
arr = np.zeros((k,k,))
idx = 0
for i in range(k):
    for j in range(i + 1, k):
        arr[i, j] = idx
        idx += 1


def parallel_calc(array, k, si, endi):
     for i in range(si, endi):
         for j in range(k):
             # do some expensive calculations

for start_i, stop_i in split_matrix(k, cpu_cnt):
     parallel_calc(arr, k, start_i, stop_i)

您对实现或库功能有什么建议吗?

Do you have any suggestions as to the implementation or library function?

推荐答案

在对侧面进行大量几何计算之后，我到达了以下分区，该分区在每个垂直方向上给出了大致相同数量的矩阵点(或水平(如果需要的话)分区.

After a number of geometrical calculations on a side I arrived at the following partitioning that gives roughly the same number of points of the matrix in each of the vertical (or horizontal, if one wants) partitions.

def offsets_for_equal_no_elems_diag_matrix(matrix_dims, num_of_partitions):
    if 2 == len(matrix_dims) and matrix_dims[0] == matrix_dims[1]:  # square
        k = matrix_dims[0]
        # equilateral right angle triangles have area of side**2/2 and from this area == 1/num_of_partitions * 1/2 * matrix_dim[0]**2 comes the below
        # the k - ... comes from the change in the axis (for the calc it is easier to start from the smallest triangle piece)
        div_points = [0, ] + [round(k * math.sqrt((i + 1)/num_of_partitions)) for i in range(num_of_partitions)]
        pairs = [(k - div_points[i + 1], k - div_points[i], ) for i in range(num_of_partitions - 1, -1, -1)]
        return pairs

这篇关于如何将对角矩阵沿一条轴分成相等数量的项?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！