Быстрое вычисление целочисленной основы для ядра матрицы с использованием графического процессора - PullRequest
Новая
       25

Быстрое вычисление целочисленной основы для ядра матрицы с использованием графического процессора

0 голосов
/ 25 декабря 2018

Ввод: n times m матрица A с целочисленными значениями.Например, рассмотрим матрицу 

A = [[2,1,0],[0,1,2]]

Вывод: целое число для ядра / пустого пространства A.Например, для вышеуказанной матрицы целочисленный базис равен 

[[1,-2,1]]

. Я использую идеи из этого сообщения stackoverflow , чтобы сначала вычислить рациональный базис, а затем вычислить целочисленный базис путем умножения насм3 знаменателей со следующим (Python 2.7) кодом: 

import numpy as np
from sympy import Matrix,lcm
from fractions import Fraction

def ker_int_basis(B):
    BKer = 1.0*np.array(Matrix(B).nullspace())
    Bk =[]
    for basis in BKer:
        l = lcm(map(lambda x: Fraction(x).limit_denominator().denominator,map(str,basis)))
        basis = map(int,l*basis)
        Bk.append(basis)    
    Bk = np.array(Bk)
    return Bk

Работает на небольших примерах.Но приведенный выше код утомительно медленный и у меня есть матрицы 10000 times 500 или больше.Приведенный выше код не выводится даже после нескольких часов работы.

Как сделать код быстрее? Я бы предпочел реализацию на GPU, учитывая, что матрицы очень очень большие.Многоядерный процессор также будет улучшением.Также приветствуются предложения по более эффективному использованию циклов и структур данных в приведенном выше коде.

1 Ответ

0 голосов
/ 25 декабря 2018

Sympy использует Гауссово исключение , чтобы вычислить пустое пространство B.Это $ O (n ^ 3) $, и я предполагаю, что это вычисление является узким местом в вашем коде (но это стоило бы проверить).

Исключение по Гауссу можно распараллелить, выполнив все исключения одновременно.Алгоритм GE относительно прост, и существует множество реализаций для чисел с плавающей запятой.Однако я не видел других символических пакетов, которые делали бы это с использованием рациональных чисел или целых чисел в моем кратком поиске (хотя вы, вероятно, могли бы реализовать это относительно легко).

Еще одна вещь, которую вы могли бы попробовать, чтобы парализоватьЗадача без переписывания алгоритма нахождения нулевого пространства состоит в том, чтобы разбить матрицу на два набора строк, вычислить нулевое пространство каждого и затем вычислить основу для пересечения вычисленных нулевых пространств.Это будет хорошо работать, если каждый из наборов строк имеет относительно небольшие пустые пространства, но не так хорошо, если они оба возвращают очень большие пустые пространства.

...