2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 [Wolfram Mathematica] Linear Solve
Сообщение28.09.2014, 13:22 
Аватара пользователя
Вкратце о задаче:
Есть небольшая квадратная матрица CK нечётной размерности $(2k+1)\times (2k+1)$, играющая роль ядра свёртки, и матрица переменных fs = Array[f, {n, n}]. Решаю уравнение ListConvolve[CK, fs] == 0 относительно тех переменных, которые попадают под центральный элемент CK при свёртке, $k$ краевых элементов полагаем параметрами.
Для этого создаю две дополнительные функции:
Код:
eqns[n_] := Map[# == 0 &, ListConvolve[CK, Array[f, {n, n}]], {2}];
An[n_] :=
  Last[CoefficientArrays[Join @@ eqns[n],
    Join @@ Array[f, {n - 2 k, n - 2 k}, {1 + k, 1 + k}]]];
bn[n_] :=
  First[CoefficientArrays[Join @@ eqns[n],
    Join @@ Array[f, {n - 2 k, n - 2 k}, {1 + k, 1 + k}]]];

И решение:
Код:
S1[n_] := Partition[LinearSolve[An[n], bn[n]], n - 2 k]
Профилируем и удивляемся:
Код:
k = 4;

In:= Table[First@Timing@LinearSolve[An[n], bn[n]], {n, 5, 12}]

Out= {0., 0.012001, 0.032002, 0.132008, 0.492031, 1.5761, 5.89637, 29.5698}
Экспоненциальная сложность!
Меняем LinearSolve[A, b] на Inverse[A].b, поскольку матрица A невырожденна:
Код:
In:= Table[First@Timing[Inverse[An[n]].bn[n]], {n, 5, 14}]

Out= {0., 0., 0., 0.008, 0.016001, 0.032002, 0.076005, 0.164011, 0.296018, 0.536034}
Ожидаемая сложность $O(n^4)$. Почему так? Неужели LinearSolve не может работать столь же быстро, как Inverse?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group