Armadillo C ++: линейная комбинация с вычислениями модуля - PullRequest
Новая
       81

Armadillo C ++: линейная комбинация с вычислениями модуля

0 голосов
/ 03 октября 2018

Я хочу извлечь линейные комбинации из матриц, но выполняя комбинации в модуле.

Давайте рассмотрим модуль расчета 5, у нас будет следующее для сложения: 

 + |  0 1 2 3 4
 --+-----------
 0 | 0 1 2 3 4
 1 | 1 2 3 4 0
 2 | 2 3 4 0 1
 3 | 3 4 0 1 2 
 4 | 4 0 1 2 3

и эта таблица для умножения: 

 * | 0 1 2 3 4
 --+-----------
 0 | 0 0 0 0 0
 1 | 0 1 2 3 4
 2 | 0 2 4 1 3
 3 | 0 3 1 4 2
 4 | 0 4 3 2 1

Итак, давайте возьмем пример: Давайте рассмотрим следующую матрицу: 

E = 2 1 3 2 0
    4 3 0 1 1

Затем мы можем получить матрицу триангуляции, применяя LUдекомпозиция (https://en.wikipedia.org/wiki/LU_decomposition) (или исключение Гаусса), которая выглядит следующим образом: 

T = 1 0 0 0 0 
    2 1 0 0 0

и, наконец, матрица, которую я хочу извлечь, - та, которая хранит линейные комбинации: 

CL = 3 2 3 0 3
     0 1 1 3 4
     0 0 1 0 0 
     0 0 0 1 0
     0 0 0 0 1

В общем, алгоритм должен работать следующим образом: 

 Input: a matrix E with n rows and m columns, and p, a prime number.

 * We perform a Gaussian elimination/LU decomposition to obtain the lower-triangulation matrix T. 
   But all the calculus are done modulo 'p'. 

 Output: T (with the same size as E, n rows m columns). 
         CL (with a size m rows, m columns), 
         which is basically the identity matrix on which we 
         applied all the modifications that were performed on E to obtain T.

Хорошо, теперь у нас есть контекст, позвольте мне объяснить проблему. Я начал это делать.используя библиотеку Armadillo (http://arma.sourceforge.net/),, но я не нашел никакого решения в библиотеке для выполнения исчисления на математическом поле стр. Я легко нашел метод LU для получения нижнего трианаGle матрицы, но вычисления выполняются в реальном. 

#include <iostream>
#include <armadillo>

using namespace arma;
using namespace std;

int main(int argc,char** argv)
{

    mat A = mat({{2,1,3,2,0},{4,3,0,1,1}});

    mat L, U, P;

    lu(L, U, P, A);

    cout << L << endl;

    return 0;
}

С помощью следующего вы получите матрицу нижнего треугольника 'L', но в реальном исчислении.Таким образом, вы получаете: 

 T' =  1   0
       1/2 1

Есть ли какой-либо метод для выполнения вычислений по модульному принципу?

EDIT Библиотека Armadillo не являетсяв состоянии сделать это.Я разработал свое собственное разложение LU по модулю, но там все еще есть ошибка.Я задал новый вопрос здесь Линейная комбинация C ++ в модуле , в надежде решить его.

1 Ответ

0 голосов
/ 03 октября 2018

Прежде всего: отбросьте using namespace s, код может стать полностью нечитаемым, если вы сделаете это.

Я еще не использовал Armadillo.Но я посмотрел на документацию, и она мне кажется шаблонной.

Теперь все становится немного диким.Тип, который вы используете, arma::mat кажется typedef для arma::Mat<double>.

Функция высокого уровня arma::lu не документирована надлежащим образом.Это очевидно делает LU-разложение, но я не знаю, является ли функция шаблонной.Если это так, то есть вы не можете просто вызывать его с помощью double матов, но также и других типов, вы можете получить снимок, используя пользовательский тип, представляющий поле (так как 5 - простое число, иначе вы были бы полностью потеряны) вычислений по модулю5. То есть вы пишете класс, давайте назовем его IntMod5 и определим все необходимые операторы для этого класса, то есть все операторы, которые использует IntMod5.Например, вам нужно определить operator/(), например, составив таблицу инверсий из 4 из 5 элементов поля (0 не имеет ни одного), то есть 1-> 1, 2-> 3, 3-> 2, 4-> 4 и определите 

IntMod5 operator/(const IntMod5& o) const
{
    return IntMod5((this->value*inverse(o.value))%5);
}

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

Прежде чем вы пройдете всю работу, вы должны использовать тривиальный класспросто заверните в двойное число и проверьте, не выполняет ли arma::Mat или arma::lu какие-либо проверки типа, блокирующие вас.

В случае неудачи вам, скорее всего, придется написать свой собственный LU-декомпозицию по модулю 5 или найти другую библиотеку.это поддерживает это.

...