Пакет линейной алгебры над целыми числами - PullRequest
Новая
       55

Пакет линейной алгебры над целыми числами

2 голосов
/ 12 ноября 2010

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

Ответы [ 5 ]

2 голосов
/ 25 ноября 2010

CVXOPT может быть вариантом. В частности, посмотрите на эту функцию: 

cvxopt.glpk.ilp = ilp(...)  
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

minimize    c'*x
subject to  G*x <= h
            A*x = b
            x[I] are all integer
            x[B] are all binary

Посмотрите также на этот пост: Решатель бинарного линейного программирования на Python

2 голосов
/ 12 ноября 2010

Вы можете использовать функцию mathnf в PARI , чтобы вычислить нормальную форму Эрмита матрицы, содержащей ваши охватывающие векторы в виде столбцов.Столбцы матрицы HNF охватывают одну и ту же решетку, и тривиально проверить, находится ли вектор в этой решетке.Есть еще много библиотек, способных вычислять HNF - Google - ваш друг.

1 голос
/ 25 ноября 2010

Возможно LinBox - это то, что вам нужно.

0 голосов
/ 05 января 2011

Лучшие библиотеки, которые я знаю для этого:

Pari (не GP, а сама библиотека Pari): http://pari.math.u -bordeaux.fr /

NTL (C ++): http://www.shoup.net/ntl/

IML: http://www.cs.uwaterloo.ca/~astorjoh/iml.html

Мы начинаем добавлять такую ​​функциональность в flint2 (в частности, в модуль fmpz_mat):

https://github.com/fredrik-johansson/flint2

Цель кремня состоит в том, чтобы сделать его абсолютно максимально быстрым, хотя материал матрицы все еще находится в стадии разработки.

0 голосов
/ 12 ноября 2010

Есть ли у LINPACK что-нибудь?

http://en.wikipedia.org/wiki/LINPACK

Раньше мы часто использовали это в мои векторные / суперкомпьютерные дни, и обычно есть аппаратные версии.

...