Может ли кто-нибудь объяснить аномальное поведение разложения LU в Revol R? - PullRequest
Новая
       67

Может ли кто-нибудь объяснить аномальное поведение разложения LU в Revol R?

2 голосов
/ 16 января 2012

Простой матричный тест показал, что Revolution Analytics R 2.13.2 Разложение LU почти в 5 раз медленнее, чем умножение матриц. Теория и многолетняя практика показывают, что LU должно составлять от 1/3 до 2/3 времени для A*A.

Revo R и Matlab используют Math Kernel от Intel для этого теста. R 2.14.1 не использует ядро. Все 64-битное.

Аномалия показана в таблице 2 ниже. Это таблица 1, нормализованная около A*A. Существуют и другие (очевидные) аномалии, но наиболее ярким является LU. 

                        Table 1 (secs)

                    A*A     LU     A\b    Det   Inv
----------------------------------------------------
R 2.14.1           0.757   0.43   0.45   0.20  1.11
Revo R 2.13.2      0.063   0.35   0.11   0.03  0.14
Matlab 2011b       0.062   0.08   0.10   0.07  0.16
----------------------------------------------------
Averaged over 20 runs on a 1000x1000 random matrix


                       Table 2 (normalized)

                    A*A     LU     A\b    Det   Inv
----------------------------------------------------
R 2.14.1             1     0.57   0.19   0.26  1.47
Revol R 2.13.2       1     4.67*  1.58   1.33  2.17
Matlab 2011b         1     0.67   1.72   0.61  1.68
----------------------------------------------------
Note: x = A\b in Matlab is x <- solve(A,b) in R.

ОБНОВЛЕНИЕ : Я последовал совету Саймона Урбанека и заменил LUP = expand(lu(Matrix(A))); на lu(A); Строки Revo R теперь 

                    Revol R 2.13.2

              A*A    LU     A\b    Det   Inv
            ---------------------------------
  time       0.104  0.107  0.110  0.042  0.231  
  norm time  1.000  1.034  1.060  0.401  2.232

Время в секундах на 

Dell Precision 690, 2 x Intel®  Xeon® E53405 CPU @ 2.33GHz,
16GB ram, 2 Processors, 8 Cores and 8 Threads, 
Windows 7 Prof., 64-bit

Отчет о незавершенном производстве, содержащий таблицы и используемый код: здесь .

ОБНОВЛЕНИЕ 2 :

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

Я перешел на новый 

Lenovo ThinkPad X220, Intel Core i7-2640M CPU @ 2.80GHz, 
8GB ram, 1 Processor, 2 Cores and 4 Threads
Windows 7 Professional, 64-bit.

Примечание : Процессор Core i7 имеет Turbo Boost от Intel , который увеличивает тактовую частоту до 3,5 ГГц, если он чувствует высокую нагрузку. Насколько я знаю, Turbo Boost не находится под управлением программы (mer) ни в одной из трех систем.

Эти изменения, я надеюсь, сделают результаты более полезными. 

                          Table 3. Times(secs)

                  A*A    chol(A)   lu(A)    qr(A)    svd(A)   eig(A)   Total
-----------------------------------------------------------------------------
R 2.14.1         0.904    0.157    0.260    0.568    4.260    6.967    13.11
Revol R 2.13.2   0.121    0.029    0.062    0.411    1.623    3.265     5.51   
Matlab 2011b     0.061    0.014    0.033    0.056    0.342    0.963     1.47       
-----------------------------------------------------------------------------
                    Times(secs) averaged over 20  runs



                          Table 4. Times(normalized)

                  A*A    chol(A)   lu(A)    qr(A)    svd(A)  eig(A)   Total
----------------------------------------------------------------------------
R 2.14.1         1.000    0.174    0.288    0.628    4.714    7.711   14.52
Revol R 2.13.2   1.000    0.237    0.515    3.411   13.469   27.095   45.73
Matlab 2011b     1.000    0.260    0.610    0.967    5.768   16.774   25.38
----------------------------------------------------------------------------
                     Times(secs) averaged over 20  runs

Из таблицы 4 видно, что ложная аномалия исчезла и все системы ведут себя так, как предсказывает теория. 

                          Table 5. Times/Matlab Times

                  A*A    chol(A)   lu(A)    qr(A)    svd(A)  eig(A)   Total
----------------------------------------------------------------------------
R 2.14.1          15      11         8       10       12       7        9
Revol R 2.13.2     2       2         2        7        5       3        4
----------------------------------------------------------------------------
                         Rounded to the nearest integer

1 Ответ

5 голосов
/ 16 января 2012

ПОЭТОМУ, вы не измеряете время разложения, а накладные расходы, которые вы создаете путем преобразования матриц все время. В обычном R: 

# actual lu call
> system.time(lu(A))
   user  system elapsed 
  0.136   0.000   0.139 
# your code
> system.time(expand(lu(Matrix(A))))
   user  system elapsed 
  0.536   0.000   0.537

так что, скорее всего, вы сами создаете накладные расходы. Это особенно важно, когда разложение происходит быстро. Также обратите внимание, что восприятие производительности «R» неоднозначно, поскольку производительность самого R сильно зависит от того, какой BLAS вы используете.

(В качестве дополнительного примечания - вы можете использовать system.time в своих тестах - вас также может заинтересовать пакет microbenchmark R)

...