Strategie di pre-computazione quando si risolvono più equazioni lineari con la stessa matrice?

Question

Strategie di pre-computazione quando si risolvono più equazioni lineari con la stessa matrice?

#1 da (1 voti)

2

Spesso nella modellazione, nell'elaborazione dei dati e nell'ottimizzazione; le porzioni intensive del codice possono spesso ridurre la risoluzione di molte equazioni lineari.

es.

solve for x1 in A x1 = b1

solve for x2 in A x2 = b2

... e così via

A volte la matrice 'A' non cambia tra i calcoli, e la mia domanda è come (e quando) posso approfittarne con qualche pre-computazione? Questo presuppone che tu stia già utilizzando librerie di algebra lineare (es. BLAS, LAPACK) ottimizzate per il tuo sistema, e non riesca a trovare un modo per risolverlo in una singola operazione batch per cui (LAPACK, Matlab, ecc.) Hanno già funzioni specializzate .

Ad esempio, una strategia consiste nel calcolare e archiviare una decomposizione della matrice appropriata (LUP o QR) una volta che sarebbe altrimenti (internamente) chiamata dalla libreria di algebra lineare ogni volta. Tuttavia, posso trovare poche indicazioni su quali utilizzare che funzionano bene con i risolutori intermedi (in particolare quando si lavora con LAPACK), o i meriti relativi delle scomposizioni in termini di velocità o in esecuzione in casi di bordo negativi.

Nota: una strategia " non valida " consiste nel calcolare la matrice inversa inv(A) a causa di problemi di velocità e accuratezza. ( La documentazione di MatLab per inv () ne discute in dettaglio)

algorithms optimization numerical-equations

posta J. Paulsen 01.06.2016 - 23:26

fonte

1 risposta

Leggi altre domande sui tag algorithms optimization numerical-equations

Quale struttura di dati IndexedDB per l'app di Chrome? Come ottenere la classe di comportamento dalla sua classe di dati quando sono separati ai fini della comunicazione server-client?

score 1 · Accepted Answer

La decomposizione della matrice è sicuramente il modo per andare qui. La scomposizione che utilizzi sarà determinata dalla struttura dei sistemi che stai cercando di risolvere: la soluzione utilizzando la decomposizione di Cholesky richiede una matrice quadrata, simmetrica, definita positiva. Puoi risolvere una matrice quadrata generale usando LU o QR. La LU viene in genere utilizzata perché di solito richiede meno passaggi rispetto a QR. Il QR è usato per sistemi sotto e sopra determinati come minimi quadrati e per trovare autovalori.

Se stai usando LAPACK, puoi chiamare dgetrf a factorize LU una matrice generale, quadrata e dgetrs per trovare la soluzione, utilizzando l'input vettore e le matrici dei fattori che hai creato con dgetrf .