Как наиболее эффективно использовать QR-разложение в Julia?

Избегание выделения массивов полезно для производительности. Однако мне еще предстоит понять, как можно наиболее эффективно выполнить QR-разложение матрицы A. (примечание: необходимы матрицы Q и R)

Простое использование Q, R = qr(A) , вероятно, не лучшая идея, поскольку он выделяет как Q, так и R, где оба могут быть перераспределены.

Функция qrfact позволяет хранить факторизацию в упакованном формате < / а>. Однако я бы все равно написал потом: F = qrfact(A); Q = F[:Q]; R = F[:R] снова выделяю новые массивы для Q и R. Наконец, в документации также предлагается функция qrfact!, которая экономит место, перезаписывая ввод A вместо создания копии. Однако, если кто-то использует F = qrfact!(A), перезаписанный A не полезен в том смысле, что он не является ни Q, ни R, который (в частности, мне) может понадобиться.

Итак, мои два вопроса:

  1. Каков наилучший / наиболее эффективный способ выполнения QR-разложения, если вас интересуют только матрицы Q и R и у вас нет проблем с их перераспределением.

  2. Что на самом деле записывается в матрице A при вызове qrfact!(A)?


performance julia linear-algebra qr-decomposition
person George Datseris    schedule 28.05.2017    source источник
comment
Зачем нужно делать Q = F[:Q]; R = F[:R] потом? Разве вы не можете просто использовать F[:Q] как есть?   -  person Michael K. Borregaard    schedule 28.05.2017
comment
Ссылки на способ хранения есть в документации Julia. В частности, это paper был связан с. Но на самом деле вам стоит взглянуть на этот код Юлии   -  person Dan Getz    schedule 28.05.2017
comment
@ MichaelK.Borregaard Для меня не имеет значения, использую ли я Q или F[:Q]. Проблема в том, как избежать выделения, сделанного из F[:Q] (если таковое имеется).   -  person George Datseris    schedule 28.05.2017
comment
Блин, к сожалению, мне нужно работать с матрицей F[:Q], потому что мне нужно изменить знак в некоторых столбцах (qr-разложение для поиска показателей ляпунова)   -  person George Datseris    schedule 28.05.2017
comment
У меня есть некоторые серьезные сомнения в том, что стоимость выделения массива (фактически O (1)) может быть даже обнаружена в алгоритме, который включает выполнение QR-разложения O (n ^ 3). Вы профилировали свой код и убедились, что вам действительно нужно избегать этих распределений?   -  person Fengyang Wang    schedule 28.05.2017

Ответы (1)


arrow_upward
4
arrow_downward

In

F = qrfact!(A)

or 

F = qrfact(A)

F[:Q] и F[:R] не выделяют новые плотные массивы; это просто представления упакованного формата, из которых легко вычисляются Q и R. Это означает, что qrfact!(A) не нужно выделять массивы для Q и R, он просто вычисляет упакованный формат для A.

Однако это также означает, что F[:Q] и F[:R] нельзя изменять. Если вам нужно изменить один из них по какой-либо причине, вам нужно collect превратить его в изменяемый Array, и это, безусловно, будет выделено. По-прежнему будет более эффективно использовать qrfact!(A) вместо qrfact(A), потому что последний будет выделять пространство для упакованного QR-факторизации, а также для collected Array.

person Fengyang Wang    schedule 28.05.2017
comment
Спасибо за ответ. Осмотревшись, я пришел к такому же выводу (F[:Q] не распределяет). Я также понял, что qrfact!(A) делает с A: он имеет те же элементы, что и R, но он не является верхним треугольником, поэтому я не знаю, что происходит с нижним треугольником. PS: Нет, я не обнаружил, что это причина того, что мой код работает медленно. Для меня это была просто возможность лучше понять, как использовать qr с Джулией. - person George Datseris; 29.05.2017
comment
Формат, который мы используем для хранения QR-факторизации, описан в - person Andreas Noack; 30.05.2017