Детерминантное значение для очень большой матрицы

У меня есть очень большая квадратная матрица порядка 100000, и я хочу знать, равно ли значение определителя этой матрице нулю или нет.

Что может быть самым быстрым способом узнать это?

Я должен реализовать это на С++


c++ algorithm matrix determinants
person jaig    schedule 11.12.2013    source источник
comment
Найдите себе хорошую реализацию BLAS и вызывайте функции, которые она вам дает.   -  person RichardPlunkett    schedule 11.12.2013
comment
это около 80 ГБ для хранения этой матрицы, вы можете переосмыслить свой подход.   -  person Anycorn    schedule 11.12.2013
comment
Для таких задач лучше использовать существующие математические библиотеки, потому что они уже проверены. Так что не реализуйте для него свою собственную детерминантную функцию! Кроме того, очень сложно вычислить определитель для такой большой матрицы. Вы уверены, что вам это действительно нужно?   -  person Ilya    schedule 11.12.2013
comment
@Илья, ну, ОП не нужно его вычислять. Он хочет знать, ноль это или нет. Это совсем другая проблема. Расчет это одно из решений. Не лучший скорее всего.   -  person luk32    schedule 11.12.2013
comment
тем не менее, несмотря на это, использование существующих библиотек — очень хороший совет.   -  person RichardPlunkett    schedule 11.12.2013
comment
На самом деле у меня есть однородный набор из n уравнений, и я хочу знать, имеет ли он тривиальное решение 0 для всех его n переменных, где n составляет около 10 ^ 5   -  person jaig    schedule 11.12.2013

Ответы (4)


arrow_upward
1
arrow_downward

Предполагая, что вы пытаетесь определить, является ли матрица несингулярной, вы можете посмотреть здесь:

https://math.stackexchange.com/questions/595/what-is-the-most-efficient-way-to-determine-if-a-matrix-is-invertible

Как упоминалось в комментариях, лучше всего использовать какую-то библиотеку BLAS, которая сделает это за вас, например Boost::uBLAS.

person en4bz    schedule 11.12.2013

arrow_upward
1
arrow_downward

Обычно матрицы такого размера чрезвычайно разрежены. Используйте алгоритмы переупорядочивания строк и столбцов, чтобы сконцентрировать записи рядом с диагональю, а затем используйте разложение QR или разложение LU. Произведение диагональных элементов второго множителя с точностью до знака в случае QR является определителем. Это все еще может быть слишком плохо обусловлено, лучший результат для ранга получается при выполнении разложения по сингулярным значениям. Однако СВД дороже.

person Lutz Lehmann    schedule 11.12.2013

arrow_upward
0
arrow_downward

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

person anavaras lamurep    schedule 11.12.2013
comment
Это просто утверждение, которое на самом деле не служит ответом на вопрос автора. Я предлагаю вам прочитать как отвечать и переформулировать свой ответ. - person brandonscript; 11.12.2013
comment
@r3mus Спасибо, если вы реализуете приведенное выше утверждение, сложность меньше, чем o (n!), Как указано в этой ссылке на [math.stack] (math.stackexchange.com /вопросы/595/) - person anavaras lamurep; 11.12.2013

arrow_upward
0
arrow_downward

Насколько мне известно, вашему приложению не нужно вычислять определитель, но ранга матрицы достаточно, чтобы проверить, имеет ли система уравнений нетривиальное решение: -

Ранг матрицы

person Vikram Bhat    schedule 11.12.2013