Solusi eksplisit cepat untuk , , angka kondisi rendah

9

Saya mencari solusi eksplisit cepat (berani saya katakan optimal?) 3x3 masalah nyata, , . $\mathbf{A}\mathbf{x} = \mathbf{b}$ $\mathbf{A} \in \mathbf{R}^{3 \times 3}, \mathbf{b} \in \mathbf{R}^{3}$

Matriks bersifat umum, tetapi dekat dengan matriks identitas dengan angka kondisi mendekati 1. Karena sebenarnya pengukuran sensor dengan presisi sekitar 5 digit, saya tidak keberatan kehilangan beberapa digit karena angka masalah. $\mathbf{A}$ $\mathbf{b}$

Tentu saja, tidak sulit untuk menghasilkan solusi eksplisit berdasarkan sejumlah metode, tetapi jika ada sesuatu yang telah terbukti optimal dalam hal jumlah FLOPS, itu akan ideal (setelah semua, seluruh masalah kemungkinan akan masuk dalam register FP!).

(Ya, rutin ini sering disebut . Saya sudah menyingkirkan buah yang menggantung rendah dan ini yang berikutnya dalam daftar profiling saya ...)

linear-solver reference-request Damien
sumber

Apakah masing masing hanya digunakan sekali, atau adakah beberapa sistem linear dengan matriks yang sama? Ini akan mengubah biaya.

A

$A$

Federico Poloni

Dalam hal ini, A hanya digunakan sekali.

Damien

14

Anda tidak dapat mengalahkan formula eksplisit. Anda dapat menuliskan formula untuk solusi pada selembar kertas. Biarkan kompiler mengoptimalkan hal-hal untuk Anda. Metode lain apa pun hampir pasti akan memiliki pernyataan atau loop (misalnya, untuk metode berulang) yang akan membuat kode Anda lebih lambat daripada kode garis lurus mana pun. $x=A^{-1}b$ iffor

Wolfgang Bangerth
sumber

9

Karena matriks sangat dekat dengan identitas, seri Neumann berikut akan menyatu dengan sangat cepat:

{SEBUAH}^{- 1} = \sum_{k = 0}^{\infty} (saya - SEBUAH)^{k}

$A^{-1} = \sum_{k=0}^\infty (I-A)^k$

Bergantung pada keakuratan yang diperlukan, bahkan mungkin cukup baik untuk memotong setelah 2 istilah:

{SEBUAH}^{- 1} \approx saya + (saya - SEBUAH) = 2 saya - SEBUAH .

$A^{-1} \approx I + (I - A) = 2I - A.$

Ini mungkin sedikit lebih cepat daripada formula langsung (seperti yang disarankan dalam jawaban Wolfgang Bangerth), meskipun dengan akurasi yang jauh lebih sedikit.

Anda bisa mendapatkan akurasi lebih dengan 3 istilah:

{SEBUAH}^{- 1} \approx saya + (saya - SEBUAH) + (saya - SEBUAH)^{2} = 3 saya - 3 SEBUAH + {SEBUAH}^{2}

$A^{-1} \approx I + (I - A) + (I-A)^2 = 3I - 3A + A^2$

tetapi jika Anda menuliskan formula entri-demi-entri untuk , Anda melihat jumlah operasi floating point yang sebanding sebagai rumus invers matriks 3x3 langsung (Anda tidak harus melakukan sebuah divisi, yang sedikit membantu). $(3I - 3A + A^2)b$

Nick Algeria
sumber

Apakah divisi masih lebih mahal daripada yang lain? Saya pikir itu adalah peninggalan masa lalu.

Federico Poloni

Divisi tidak menyalurkan dengan baik satu arsitektur (ARM adalah contoh kontemporer)

Damien

@FedericoPoloni Dengan Cuda, Anda dapat melihat throughput instruksi di sini , enam kali lebih tinggi untuk perkalian / penambahan daripada divisi.

Kirill

@ Damen dan Kirill, begitu, terima kasih untuk petunjuknya.

Federico Poloni

5

Hitung FLOPS berdasarkan saran di atas:

LU, tidak berputar:
- Mul = 11, Div / Recip = 6, Tambah / Sub = 11, Total = 28; atau
- Mul = 16, Div / Recip = 3, Tambah / Sub = 11, Total = 30
Eliminasi Gaussian dengan substitusi balik, tanpa berputar:
- Mul = 11, Div / Recip = 6, Tambah / Sub = 11, Total = 28; atau
- Mul = 16, Div / Recip = 3, Tambah / Sub = 11, Total = 30
Aturan Cramer melalui ekspansi kofaktor
- Mul = 24, Div = 3, Tambah / Sub = 15, Total = 42; atau
- Mul = 27, Div = 1, Tambah / Sub = 15, Total = 43
Terbalik secara eksplisit, lalu gandakan:
- Mul = 30, Div = 3, Tambah / Sub = 17, Total = 50; atau
- Mul = 33, Div = 1, Tambah / Sub = 17, Total = 51

MATLAB proof-of-concept:

Aturan Cramer melalui Ekspansi Cofactor :

function k = CramersRule(A, m)
%
% FLOPS:
%
% Multiplications:        24
% Subtractions/Additions: 15
% Divisions:               3
%
% Total:                  42

a = A(1,1);
b = A(1,2);
c = A(1,3);

d = A(2,1);
e = A(2,2);
f = A(2,3);

g = A(3,1);
h = A(3,2);
i = A(3,3);

x = m(1);
y = m(2);
z = m(3);

ei = e*i;
fh = f*h;

di = d*i;
fg = f*g;

dh = d*h;
eg = e*g;

ei_m_fh = ei - fh;
di_m_fg = di - fg;
dh_m_eg = dh - eg;

yi = y*i;
fz = f*z;

yh = y*h;
ez = e*z;

yi_m_fz = yi - fz;
yh_m_ez = yh - ez;

dz = d*z;
yg = y*g;

dz_m_yg = dz - yg;
ez_m_yh = ez - yh;


det_a = a*ei_m_fh - b*di_m_fg + c*dh_m_eg;
det_1 = x*ei_m_fh - b*yi_m_fz + c*yh_m_ez;
det_2 = a*yi_m_fz - x*di_m_fg + c*dz_m_yg;
det_3 = a*ez_m_yh - b*dz_m_yg + x*dh_m_eg;


p = det_1 / det_a;
q = det_2 / det_a;
r = det_3 / det_a;

k = [p;q;r];

LU (tidak berputar) dan substitusi balik:

function [x, y, L, U] = LUSolve(A, b)
% Total FLOPS count:     (w/ Mods)
%
% Multiplications:  11    16
% Divisions/Recip:   6     3
% Add/Subtractions: 11    11
% Total =           28    30
%

A11 = A(1,1);
A12 = A(1,2);
A13 = A(1,3);

A21 = A(2,1);
A22 = A(2,2);
A23 = A(2,3);

A31 = A(3,1);
A32 = A(3,2);
A33 = A(3,3);

b1 = b(1);
b2 = b(2);
b3 = b(3);

L11 = 1;
L22 = 1;
L33 = 1;

U11 = A11;
U12 = A12;
U13 = A13;

L21 = A21 / U11;
L31 = A31 / U11;

U22 = (A22 - L21*U12);
L32 = (A32 - L31*U12) / U22;

U23 = (A23 - L21*U13);

U33 = (A33 - L31*U13 - L32*U23);

y1 = b1;
y2 = b2 - L21*y1;
y3 = b3 - L31*y1 - L32*y2;

x3 = (y3                  ) / U33;
x2 = (y2 -          U23*x3) / U22;
x1 = (y1 - U12*x2 - U13*x3) / U11;

L = [ ...
    L11,   0,   0;
    L21, L22,   0;
    L31, L32, L33];

U = [ ...
    U11, U12, U13;
      0, U22, U23;
      0,   0, U33];

x = [x1;x2;x3];
y = [y1;y2;y3];

Terbalik secara eksplisit, lalu gandakan:

function x = ExplicitInverseMultiply(A, m)
%
% FLOPS count:                  Alternative
%
% Multiplications:        30            33
% Divisions:               3             1
% Additions/Subtractions: 17            17
% Total:                  50            51


a = A(1,1);
b = A(1,2);
c = A(1,3);

d = A(2,1);
e = A(2,2);
f = A(2,3);

g = A(3,1);
h = A(3,2);
i = A(3,3);

ae = a*e;
af = a*f;
ah = a*h;
ai = a*i;

bd = b*d;
bf = b*f;
bg = b*g;
bi = b*i;

cd = c*d;
ce = c*e;
cg = c*g;
ch = c*h;

dh = d*h;
di = d*i;

eg = e*g;
ei = e*i;

fg = f*g;
fh = f*h;

dh_m_eg = (dh - eg);
ei_m_fh = (ei - fh);
fg_m_di = (fg - di);

A = ei_m_fh;
B = fg_m_di;
C = dh_m_eg;
D = (ch - bi);
E = (ai - cg);
F = (bg - ah);
G = (bf - ce);
H = (cd - af);
I = (ae - bd);

det_A = a*ei_m_fh + b*fg_m_di + c*dh_m_eg;

x1 =  (A*m(1) + D*m(2) + G*m(3)) / det_A;
x2 =  (B*m(1) + E*m(2) + H*m(3)) / det_A;
x3 =  (C*m(1) + F*m(2) + I*m(3)) / det_A;

x = [x1;x2;x3];

Eliminasi Gaussian:

function x = GaussianEliminationSolve(A, m)
%
% FLOPS Count:      Min   Alternate
%
% Multiplications:  11    16
% Divisions:         6     3
% Add/Subtractions: 11    11
% Total:            28    30
%

a = A(1,1);
b = A(1,2);
c = A(1,3);

d = A(2,1);
e = A(2,2);
f = A(2,3);

g = A(3,1);
h = A(3,2);
i = A(3,3);

b1 = m(1);
b2 = m(2);
b3 = m(3);

% Get to echelon form

op1 = d/a;

e_dash  = e  - op1*b;
f_dash  = f  - op1*c;
b2_dash = b2 - op1*b1;

op2 = g/a;

h_dash  = h  - op2*b;
i_dash  = i  - op2*c;
b3_dash = b3 - op2*b1; 

op3 = h_dash / e_dash;

i_dash2  = i_dash  - op3*f_dash;
b3_dash2 = b3_dash - op3*b2_dash;

% Back substitution

x3 = (b3_dash2                  ) / i_dash2;
x2 = (b2_dash        - f_dash*x3) / e_dash;
x1 = (b1      - b*x2 -      c*x3) / a;

x = [x1 ; x2 ; x3];

Catatan: Silakan menambahkan metode dan jumlah Anda sendiri ke pos ini.

Damien
sumber

Apakah Anda menghitung waktu yang diperlukan untuk menyelesaikan dengan dua metode?

nicoguaro

Tidak. Kode di atas tidak akan berjalan dengan cepat sama sekali. Intinya adalah untuk mendapatkan jumlah FLOPS eksplisit dan menyediakan kode untuk ditinjau jika saya melewatkan sesuatu,

Damien

Dalam LU, 5 divisi dapat dikonversi menjadi 5 MUL dengan mengorbankan 2 operasi timbal balik tambahan (yaitu 1 / U11 dan 1 / U22). Itu akan menjadi spesifik untuk apakah ada keuntungan yang harus dibuat di sana.

Damien

2

A^{- 1} b

$A^{-1}b$

2 b - A b

$2b - Ab$

A^{- 1} b

$A^{-1}b$

3 (b - A b) + A^{2} b

$3(b - Ab) + A^2b$

A^{- 1} b

$A^{-1}b$ terlihat 33 perkalian, 17 tambahan / pengurangan, dan 1 divisi. Seperti yang saya katakan, nomor saya mungkin tidak aktif, jadi Anda mungkin ingin memeriksa ulang.

Geoff Oxberry

@ GeoffOxberry, saya akan memeriksanya dan melaporkan.

Damien

4

Mungkin Aturan Cramer. Jika Anda dapat menghindari pivot, mungkin faktorisasi LU; ini adalah matriks 3x3, jadi membuka gulungan secara manual akan mudah. Hal lain mungkin akan melibatkan percabangan, dan saya ragu bahwa metode ruang bagian Krylov akan cukup sering bertemu dalam 1 atau 2 iterates agar layak.

Geoff Oxberry
sumber

Solusi eksplisit cepat untuk , , angka kondisi rendah

Jawaban: