boost::ublas как получить определитель матрицы int?

Я нашел функцию, которая вычисляет определитель матрицы boost::ublas:

template<typename ValType>
ValType det_fast(const ublas::matrix<ValType>& matrix)
{
    // create a working copy of the input 
    ublas::matrix<ValType> mLu(matrix);
    ublas::permutation_matrix<std::size_t> pivots(matrix.size1());

    auto isSingular = ublas::lu_factorize(mLu, pivots);
    if (isSingular)
        return static_cast<ValType>(0);

    ValType det = static_cast<ValType>(1);
    for (std::size_t i = 0; i < pivots.size(); ++i) 
    {
        if (pivots(i) != i)
            det *= static_cast<ValType>(-1);

        det *= mLu(i, i);
    }

    return det;
}

Эта функция отлично работает, но только с нецелочисленными типами (отлично работает с float и double). Когда я пытаюсь передать ту же матрицу, но с типом int, я получаю ошибку компиляции:

Ошибка проверки в файле c:\boost\boost

template<typename ValType>
ValType det_fast(const ublas::matrix<ValType>& matrix)
{
    // create a working copy of the input 
    ublas::matrix<ValType> mLu(matrix);
    ublas::permutation_matrix<std::size_t> pivots(matrix.size1());

    auto isSingular = ublas::lu_factorize(mLu, pivots);
    if (isSingular)
        return static_cast<ValType>(0);

    ValType det = static_cast<ValType>(1);
    for (std::size_t i = 0; i < pivots.size(); ++i) 
    {
        if (pivots(i) != i)
            det *= static_cast<ValType>(-1);

        det *= mLu(i, i);
    }

    return det;
}
58_0\boost\numeric\ublas\lu.hpp в строке 167: единственное число != 0 || detail::expression_type_check (prod (triangular_adaptor (m), triangular_adaptor (m)), cm) неизвестное местоположение (0): фатальная ошибка в «BaseTest»: std::logic_error: внутренняя логика

Это баг буста или у меня неправильная функция? Какие изменения я мог бы сделать, чтобы избежать этой ошибки?


person AeroSun    schedule 26.04.2015    source источник


Ответы (1)


Конечно это не баг, т.к. такие проверки есть по всему uBLAS. Я предполагаю, что это потому, что большинство его операций не имеют смысла для неплавающих типов.

Вы можете отключить проверку типов, используя

#define BOOST_UBLAS_TYPE_CHECK 0

раньше включает. Но подумайте дважды! Взгляните на пример

#include <iostream>
#define BOOST_UBLAS_TYPE_CHECK 0
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/lu.hpp>
namespace ublas = boost::numeric::ublas;

template<typename ValType>
ValType det_fast(const ublas::matrix<ValType>& matrix)
{
    // create a working copy of the input 
    ublas::matrix<ValType> mLu(matrix);
    ublas::permutation_matrix<std::size_t> pivots(matrix.size1());

    auto isSingular = ublas::lu_factorize(mLu, pivots);
    if (isSingular)
        return static_cast<ValType>(0);

    ValType det = static_cast<ValType>(1);
    for (std::size_t i = 0; i < pivots.size(); ++i) 
    {
        if (pivots(i) != i)
            det *= static_cast<ValType>(-1);

        det *= mLu(i, i);
    }

    return det;
}

int main()
{
    ublas::matrix<int> m (3, 3);
    for (unsigned i = 0; i < m.size1 (); ++ i)
        for (unsigned j = 0; j < m.size2 (); ++ j)
            m (i, j) = 3 * i + j;
    std::cout << det_fast(m) << std::endl;
}

Очевидно, что матрица m сингулярна, и при смене типа с int на double функции возвращают ноль. Но с int возвращается -48.

ИЗМЕНИТЬ №1

Кроме того, вы можете создать ublas::matrix<int> без ошибок и назначить его ublas::matrix<float>. Таким образом, один из способов правильно вычислить определитель — перегрузить оператор det_fast и удалить оператор define.

int det_fast(const ublas::matrix<int>& matrix)
{
    return (int)det_fast(ublas::matrix<float>(matrix));
}

РЕДАКТИРОВАНИЕ №2

Взгляните на таблицу, где average time - время вычисления полного определителя (для int с операцией копирования) 5 запусков программы.

size |  average time, ms
------------------------
     |    int      float
------------------------
100  |    9.0        9.0
200  |   46.6       46.8
300  |  156.4      159.4
400  |  337.4      331.4
500  |  590.8      609.2
600  |  928.2     1009.4
700  | 1493.8     1525.2
800  | 2162.8     2231.0
900  | 3184.2     3025.2

Можно подумать, что для int быстрее, но это не так. В среднем для большего количества прогонов я уверен, что вы получите небольшое ускорение с float (я думаю, около 0-15 мс, что является ошибкой измерения времени). Также, если мы измерим время копирования, мы увидим, что для размера матрицы менее 3000 x 3000 оно близко к нулю (оно также составляет около 0-15 мс, что является ошибкой измерения времени). Для больших матриц время копирования увеличивается (например, для матрицы 5000 x 5000 оно составляет 125 мс). Но есть одно важное замечание! Время копирования составляет менее 1,0% всех вычислений определителя для матрицы типа int и значительно уменьшается с увеличением размера!

Все эти меры были сделаны для программы, скомпилированной с помощью Visual Studio 2013 в конфигурации выпуска с версией boost 1.58. Время измерялось с помощью функции clock. Процессор Intel Xeon E5645 2,4 ГГц.

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

person NikolayK    schedule 26.04.2015
comment
Но есть баг! Хммм, так что буст убласа didt aplicable for integer types? And there are no any way to fix it? Iti действительно грустный, поэтому я должен реализовать собственные типы данных и операции для целочисленных матриц.. - person AeroSun; 27.04.2015
comment
Николай, в вашем примере матрица действительно сингулярная, но почему она не работает, например на этой матрице: {{4,5,6}{3,9,1}{7,8,2}} ? Эта матрица невырожденная, но она не работает с той же ошибкой, что и сингулярная !=0. - person AeroSun; 27.04.2015
comment
@AeroSun Это не удается не потому, что оно единственное, а из-за проверки типа. Посмотрите на действующую версию. Определитель рассчитан правильно и равен -189 для float и double. Для int значение явно неверное - -378. Если вы удалите оператор define, вы получите ошибку, поскольку uBLAS предназначен только для плавающих типов. Также разложение LU не имеет смысла для целочисленных типов, так что это не ошибка. - person NikolayK; 27.04.2015
comment
Хорошо, это работает (это слишком просто:)). Но за исключением того, что в этом случае создается копия матрицы int.... ничего бесплатного в этом мире... спасибо!) - person AeroSun; 27.04.2015
comment
Я сделал последовательность измерений производительности с различными размерами матрицы (от 10x10 до 1000x1000), и всегда функция det_fast для матрицы int работает быстрее, чем непосредственно det_fast для матрицы с плавающей запятой. Я не понял почему....не могли бы вы объяснить? - person AeroSun; 28.04.2015
comment
@AeroSun смотрите мой РЕДАКТИРОВАТЬ #2 - person NikolayK; 28.04.2015