Rozwiązywanie układu liniowego z argumentami macierzowymi

10

Wszyscy znamy wiele metod obliczeniowych do rozwiązania standardowego układu liniowego

A x = b .

$Ax=b.$ Jestem jednak ciekawy, czy istnieją jakieś „standardowe” metody obliczeniowe do rozwiązania bardziej ogólnego (skończonego wymiaru) układu liniowego formy

L A = B,

$LA=B,$ gdzie, powiedzmy, jest macierzą , jest macierzą , a jest operatorem liniowym przenoszącym macierze do macierzy , co nie wymaga wektoryzacji macierze , tj. konwertując wszystko do standardowej postaci

.

A

$A$

m_{1} \times n_{1}

$m_1\times n_1$

B

$B$

m_{2} \times n_{2}

$m_2\times n_2$

L

$L$

m_{1} \times n_{1}

$m_1\times n_1$

m_{2} \times n_{2}

$m_2\times n_2$

A x = b

$Ax=b$

Pytam o to, że trzeba rozwiązać następujące równanie dla $u$ :

(R^{*} R + λ I) u = f

$(R^*R+\lambda I)u=f$ gdzie

R

$R$ jest 2d transformacją radonową,

R^{*}

$R^*$ jej przyległością, a zarówno

u

$u$ i

f

$f$ są tablicami 2d (obrazy). Możliwe jest wektoryzowanie tego równania, ale jest to uciążliwe, szczególnie jeśli przejdziemy do 3D.

Mówiąc bardziej ogólnie, co o $nD$ tablic? Na przykład, rozwiązywanie $LA=B$ gdzie $A$ i $B$ są tablicami 3D (w pewnym momencie będę musiał to zrobić z transformacją Radona).

Dzięki z wyprzedzeniem i jeśli czujesz taką potrzebę, możesz wysłać mnie do innego StackExchange.

linear-algebra

— icurays1
źródło

1

Możesz być w stanie zbudować skuteczny wielopoziomowy warunek wstępny, a następnie użyć gradientu sprzężonego. Mam podobny problem, gdy jest to dość skuteczne i bardzo możliwe do zrównoleglenia. Jeśli chcesz bezpośrednich metod, rozważ redukcje do postaci Schur jak w tym artykule na temat równania Lapunowa

— Nick Alger

Doskonale, dzięki za referencje! Właśnie sprawiłem, że CG działa skutecznie, więc jestem szczęśliwy.

— icurays1

9

$\mathbb{R}^n$ $\langle y, x\rangle\triangleq \mathop{\textrm{Re}}(y^Hx)$

Jedną z rzeczy, na które musisz uważać, wdrażając CG (lub podobne podejścia iteracyjne) z ogólnymi operatorami liniowymi, jest prawidłowe zaimplementowanie połączenia operatora liniowego. Oznacza to, że ludzie często mają rację , ale popełniają błąd, implementując . $y=F(x)$ $z=F^*(y)$

Zalecam wdrożenie prostego testu, który wykorzystuje następującą tożsamość: dla każdego zgodnego i , Więc co zrobić, to generuje losowe wartości i , uruchom je za pośrednictwem swoich operacjach typu forward i adjoint, odpowiednio, i obliczyć dwa produkty wewnętrzne powyżej. Upewnij się, że pasują z odpowiednią dokładnością, i powtórz kilka razy. $x$ $y$

⟨ y, F (x) ⟩ = ⟨ F^{*} (y), x ⟩ .

$\langle y, F(x) \rangle = \langle F^*(y), x \rangle.$

x

$x$

y

$y$

EDYCJA: co robisz, jeśli twój operator liniowy ma być symetryczny? Musisz także zweryfikować tę symetrię. Więc korzystać z tego samego testu, po prostu zauważając, że --- zastosować tę samą operację i . Oczywiście, OP ma zarówno operatora asymetrycznego, jak i symetrycznego do obsługi ... $F=F^*$ $x$ $y$

— Michael Grant
źródło

Dzięki @ChristianClason! Wiem z doświadczenia, jak frustrujące mogą być błędy w połączonych obliczeniach. :) W naszym pakiecie TFOCS wdrożyliśmy linop_test.mprocedurę z tego powodu. Pakiet ten obsługuje również macierze, tablice i produkty kartezjańskie w przestrzeniach wektorowych.

— Michael Grant,

3

Jak się okazuje, ponieważ mój układ jest symetryczny i dodatnio określony (ponieważ mój operator liniowy jest zapisany jako ), gradient sprzężony można dostosować w celu iteracyjnego rozwiązania tego typu równania. Jedyną modyfikacją jest obliczanie produktów wewnętrznych - tzn. Typowe obliczenia produktów wewnętrznych w CG wyglądają jak lub . W zmodyfikowanej wersji używamy produktu wewnętrznego Frobenius, który można obliczyć, sumując wpisy produktu Hadamarda (punktowo). To znaczy $R^*R+\lambda I$ $r_k^Tr_k$ $p_k^TAp_k$

⟨ A, B ⟩ = \sum_{i, j} A_{i j} B_{i j}

$\langle A,B\rangle=\sum_{i,j}A_{ij}B_{ij}$

Podejrzewam, że przejdzie to dobrze po uaktualnieniu do tablic 3D, chociaż jeszcze nie widziałem produktu wewnętrznego Frobenius zdefiniowanego na tablicach 3D (będę działał przy założeniu, że znów mogę po prostu zsumować produkt punktowy).

Nadal byłbym zainteresowany bardziej ogólnymi metodami, jeśli ktoś o nich wie!

— icurays1
źródło