Metody bez matic - Matrix-free methods

v výpočetní matematika, a bezmaticová metoda je algoritmus pro řešení a lineární soustava rovnic nebo vlastní číslo problém, který neukládá koeficient matice explicitně, ale přistupuje k matici hodnocením produktů matice-vektor.[1] Takové metody mohou být výhodné, když je matice tak velká, že její skladování a manipulace by stála spoustu paměti a výpočetního času, a to i při použití metod pro řídké matice. Mnoho iterační metody umožnit implementaci bez matice, včetně:

Distribuovaná řešení byla také prozkoumána pomocí hrubozrnných paralelních softwarových systémů k dosažení homogenních řešení lineárních systémů.[6]

Obvykle se používá při řešení nelineárních rovnic, jako jsou Eulerovy rovnice v Výpočetní dynamika tekutin. V nelineárním elasto-plastickém řešení konečných prvků byla použita metoda maticového gradientového konjugátu [7] . Řešení těchto rovnic vyžaduje výpočet jacobian což je nákladné z hlediska času a úložiště CPU. Aby se tomuto nákladu zabránilo, používají se metody bez matice. Aby se odstranila potřeba výpočtu jacobian, je místo toho vytvořen jacobian vektorový produkt, který je ve skutečnosti vektorem samotným. Manipulace a výpočet tohoto vektoru je jednodušší než práce s velkou maticí nebo lineárním systémem.

Reference

  1. ^ Langville, Amy N.; Meyer, Carl D. (2006), Google PageRank a další: věda o hodnocení vyhledávačů, Princeton University Press, str. 40, ISBN  978-0-691-12202-1
  2. ^ Coppersmith, Don (1993), „Řešení lineárních rovnic přes GF (2): Block Lanczosův algoritmus“, Lineární algebra a její aplikace, 192: 33–60, doi:10.1016 / 0024-3795 (93) 90235-G
  3. ^ Knyazev, Andrew V. (2001). "Směrem k optimálnímu předkondicionovanému vlastnímu řešení: lokálně optimální bloková předkondicionovaná metoda konjugovaného přechodu". SIAM Journal on Scientific Computing. 23 (2): 517–541. CiteSeerX  10.1.1.34.2862. doi:10.1137 / S1064827500366124.
  4. ^ Wiedemann, D. (1986), "Řešení řídkých lineárních rovnic přes konečná pole" (PDF), Transakce IEEE na teorii informací, 32: 54–62, doi:10.1109 / TIT.1986.1057137
  5. ^ Lamacchia, B. A .; Odlyzko, A. M. (1991), „Řešení velkých řídkých lineárních systémů přes konečná pole“, Pokroky v kryptologii - CRYPT0 '90, Přednášky v informatice, 537, str. 109, doi:10.1007/3-540-38424-3_8, ISBN  978-3-540-54508-8
  6. ^ Kaltofen, E .; Lobo, A. (1996), „Distribuované maticové řešení velkých řídkých lineárních systémů přes konečná pole“, Algorithmica, 24 (3–4), s. 311–348, CiteSeerX  10.1.1.17.7470, doi:10.1007 / PL00008266
  7. ^ Prabhune, Bhagyashree C .; Krishnan, Suresh (4. března 2020). „Rychlý elasto-plastový řešič bez matrice pro predikci zbytkových napětí v aditivní výrobě“. Počítačem podporovaný design. 123: 102829. doi:10.1016 / j.cad.2020.102829.