En matemática computacional , un método sin matrices es un algoritmo para resolver un sistema lineal de ecuaciones o un problema de valor propio que no almacena la matriz de coeficientes explícitamente, pero accede a la matriz evaluando productos matriz-vector. [1] Estos métodos pueden ser preferibles cuando la matriz es tan grande que almacenarla y manipularla costaría mucha memoria y tiempo de cálculo, incluso con el uso de métodos para matrices dispersas . Muchos métodos iterativos permiten una implementación sin matrices, que incluyen:
- el método de poder ,
- el algoritmo de Lanczos , [2]
- Método de gradiente conjugado preacondicionado en bloque localmente óptimo ( LOBPCG ), [3]
- Algoritmo de recurrencia de coordenadas de Wiedemann, [4] y
- el método de gradiente conjugado . [5]
También se han explorado soluciones distribuidas utilizando sistemas de software paralelos de grano grueso para lograr soluciones homogéneas de sistemas lineales. [6]
Generalmente se usa para resolver ecuaciones no lineales como las ecuaciones de Euler en Dinámica de fluidos computacional . El método de gradiente conjugado sin matriz se ha aplicado en el solucionador de elementos finitos elastoplásticos no lineales. [7] Resolver estas ecuaciones requiere el cálculo del jacobiano, que es costoso en términos de tiempo de CPU y almacenamiento. Para evitar este gasto, se emplean métodos libres de matrices. Para eliminar la necesidad de calcular el jacobiano, en su lugar se forma el producto vectorial jacobiano, que de hecho es un vector en sí mismo. Manipular y calcular este vector es más fácil que trabajar con una matriz grande o un sistema lineal.
Referencias
- ^ Langville, Amy N .; Meyer, Carl D. (2006), PageRank de Google y más allá: la ciencia de las clasificaciones de motores de búsqueda , Princeton University Press , p. 40, ISBN 978-0-691-12202-1
- ^ Coppersmith, Don (1993), "Resolver ecuaciones lineales sobre GF (2): algoritmo de bloque de Lanczos", Álgebra lineal y sus aplicaciones , 192 : 33–60, doi : 10.1016 / 0024-3795 (93) 90235-G
- ^ Knyazev, Andrew V. (2001). "Hacia el Eigensolver preacondicionado óptimo: método de gradiente conjugado preacondicionado en bloque localmente óptimo". Revista SIAM de Computación Científica . 23 (2): 517–541. CiteSeerX 10.1.1.34.2862 . doi : 10.1137 / S1064827500366124 .
- ^ Wiedemann, D. (1986), "Resolver ecuaciones lineales dispersas sobre campos finitos" (PDF) , IEEE Transactions on Information Theory , 32 : 54–62, doi : 10.1109 / TIT.1986.1057137
- ^ Lamacchia, BA; Odlyzko, AM (1991), "Resolver grandes sistemas lineales dispersos sobre campos finitos", Avances en criptología-CRYPT0 '90 , Notas de conferencias en Ciencias de la Computación, 537 , p. 109, doi : 10.1007 / 3-540-38424-3_8 , ISBN 978-3-540-54508-8
- ^ Kaltofen, E .; Lobo, A. (1996), "Solución distribuida sin matrices de grandes sistemas lineales dispersos sobre campos finitos", Algorithmica , 24 (3–4), págs. 311–348, CiteSeerX 10.1.1.17.7470 , doi : 10.1007 / PL00008266
- ^ Prabhune, Bhagyashree C .; Krishnan, Suresh (4 de marzo de 2020). "Un solucionador de elastoplástico rápido sin matriz para predecir tensiones residuales en la fabricación aditiva" . Diseño asistido por computadora . 123 : 102829. doi : 10.1016 / j.cad.2020.102829 .