Risolvere Ax = b dove A è troppo grande per essere memorizzato in un singolo array

Question

Problema: A è quadrato, a pieno rango, sparse e a bande. Ha troppi elementi da memorizzare come una singola matrice in Matlab (almeno ~ 4.6 * 10 e idealmente ~ 10 , entrambi superano lo max array size. MODIFICA: A è memorizzato come sparse, e il problema non è con memoria limitata ma con un numero limitato di elementi). Pertanto devo memorizzarlo come una raccolta di array più piccoli (righe/diagonali/colonne/blocchi).

In cerca di: un modo per risolvere Ax = b, con A dato come raccolta di array più piccoli. Idealmente in Matlab, ma non è un must.
In alternativa, se non in Matlab: forse c'è un programma in grado di archiviare e risolvere una A così grande?

Trovato finora: metodi se A è tri/pentadiagonale, ma il mio A ha N diagonali. Ho anche trovato qualcosa sul partizionamento A sui blocchi, ma non sono riuscito a trovare un modo per risolvere un sistema lineare con questi blocchi.

p.s. Il sistema è a 64 bit.

Grazie a tutti!

Answer 1

Se si ha accesso a Toolbox Parallel Computing di MATLAB con MATLAB Distributed Computing Server, si può essere in grado di memorizzare A come distributed array, in altre parole un singolo array i cui elementi sono distribuiti attraverso i ricordi di più macchine in un cluster . Puoi chiamare il comando backslash di MATLAB direttamente su un array distribuito, e MATLAB gestisce la parallelizzazione per te.

Answer 2

Se non si utilizza Matlab, è possibile archiviare array più grandi. ROOT è un framework open source sviluppato al CERN che ha interfacce C++ e Python e una varietà di solutori. È anche in grado di gestire enormi set di dati e ha anche una varietà di strumenti di visualizzazione e analisi.

Se sei interessato a scrivere C o Fortran BLAS(Basic Linear Algebra Subroutines) e CBLAS sarebbero buone opzioni. Ci sono molte implementazioni open source e proprietarie di BLAS che dovrebbero essere disponibili per la maggior parte delle distribuzioni Linux/UNIX. Ci sono anche molti esempi che mostrano come usare le subroutine BLAS in C e il codice Fortran disponibile online.

Answer 3

Ho voluto inserire questo come commento, ma penso che sia meglio dichiararlo come una risposta. Hai un problema serio. Non è solo un problema di indicizzazione, è anche un problema di memoria: 4.6x10^18 è enorme. Questo è 4,6 elementi exa. Se li memorizzi come vera precisione singola, hai bisogno di 4x4.6 exabyte di memoria. Un computer che ha una memoria così grande, non esiste ancora per mia conoscenza. Sarà necessario raccogliere tutta la memoria (disco rigido, non RAM) di una percentuale significativa di tutti i computer del mondo per memorizzare una matrice di questo tipo. Pensaci. Passare a 10^40 elementi è quasi impraticabile per il momento. Con i tuoi computer a 64 bit, lo spazio di indirizzamento a 64 bit può sopportare soppesamente 4.6x10^18 elementi. L'indirizzo a 64 bit (o intero) rende possibile l'indicizzazione diretta di 2^64 elementi che è approssimativamente 16x10^18. Quindi devi pensarci due volte.

Tornando al problema in sé, ci sono possibilità che tu possa trasformare la tua matrice in un operatore implicito. Per operatore implicito, voglio dire, non hai bisogno di memorizzarlo, perché ha un modello che sai come riprodurre, oppure puoi applicarlo a un vettore senza effettivamente formare la matrice. Se hai la matrice in mano, sei molto probabile in questa situazione, considerando quello che ho detto sopra. Se questo è il caso, per risolvere il tuo problema, devi semplicemente usare un solver iterativo e fornire una scatola nera che faccia la tua moltiplicazione di matrice.Andare in altre direzioni potrebbe essere uno spreco di tempo.