Utilizzo di CUDA per risolvere un sistema di equazioni in modo non lineare lineare al quadrato

Question

Utilizzando CUDA, vorrei risolvere un sistema di equazioni con un risolutore dei minimi quadrati non lineare. Questi metodi sono discussi in un eccellente opuscolo che può essere scaricato here.

La matrice Jacobiana nel mio problema è triangolare sparsa e inferiore. È disponibile una libreria per CUDA con questi metodi, o dovrò programmare questi metodi personalmente dal libretto?

È un risolutore di minimi quadrati non lineare di Gauss-Newton, Levenberg-Marquardt o Risolutore di metodo di Powell disponibile in una libreria CUDA (gratuita o non libera)?

Answer 1

Prima indicando una possibile, semplice implementazione di un procedura di ottimizzazione quasi-Newton in CUDA, alcune parole su come funziona un ottimizzatore quasi-Newton.

Consideriamo una funzione f di N variabili reali x e fare una seconda espansione ordine intorno a un certo punto xi:

dove A è la matrice Hessiana .

Per trovare un minimo a partire da un punto xi, il metodo di Newton consiste di costringere

che comporta

e che, a sua volta, implica conoscere l'inverso della tela di iuta.Inoltre, per garantire la funzione diminuisce, la direzione aggiornamento

dovrebbe essere tale che

che implica che

Secondo la suddetta diseguaglianza , la matrice dell'Assia dovrebbe essere positivo definito. Sfortunatamente, la matrice hessiana non è necessariamente definita positiva, specialmente lontano da un minimo di f, quindi usare l'inverso dell'essia, oltre ad essere computazionalmente appesantito, può essere anche deleteria, spingendo la procedura ancora più lontano dal minimo verso le regioni di valori crescenti di f. In generale, è più conveniente usare un metodo quasi-Newton, cioè un'approssimazione dell'inversa della Hesse, che rimane definita positiva e aggiorna l'iterazione dopo le iterazioni che convergono all'inverso dell'Hesse stessa. Una giustificazione approssimativa di un metodo quasi-Newton è la seguente. Considerare

e

Sottraendo le due equazioni, abbiamo la regola di aggiornamento per la procedura di Newton

La regola di aggiornamento per il quasi- La procedura di Newton è la seguente

dove Hi + 1 è la matrice menzionato approssimare l'inverso dell'Hessiana e aggiornamento passo dopo passo.

Esistono diverse regole per l'aggiornamento Hi + 1 e non sto entrando nei dettagli di questo punto. Uno molto comune è fornito dallo Broyden-Fletcher-Goldfarb-Shanno, ma in molti casi lo schema Polak-Ribiére è sufficientemente efficace.

L'implementazione CUDA possono seguire la stessa procedura dell'approccio classico Numerical Recipes, ma tenendo conto che:

1) vettori e matrici operazioni possono essere efficacemente realizzati mediante CUDA spinta o cuBLAS; 2) La logica di controllo può essere eseguita dalla CPU; 3) La minimizzazione della linea, che comprende il bracketing delle radici e i riscontri delle radici, può essere eseguita sulla CPU, accelerando solo le valutazioni dei costi funzionali e del gradiente della GPU.

Con lo schema precedente, incognite, gradienti e Hessian possono essere mantenuti sul dispositivo senza che sia necessario spostarli avanti e indietro da un host all'altro.

prega, si noti anche che alcuni approcci sono disponibili in letteratura in cui tentano di parallelizzare la minimizzazione linea sono anche proposti, vedi

Y. Fei, G. Rong, B. Wang, W. Wang, " Algoritmo parallelo L-BFGS-B su GPU ", Computer & Grafica, vol. 40, 2014, pp. 1-9.

A questo github page, un'implementazione completa CUDA è disponibile, generalizzando l'approccio Numerical Recipes impiegando linmin, mkbrak e dbrent al caso GPU parallelo. Questo approccio implementa lo schema di Polak-Ribiére, ma può essere facilmente generalizzato ad altri problemi di ottimizzazione quasi-Newton.

Answer 2

Attualmente non esistono procedure disponibili in nessuna libreria che implementa la risoluzione di un sistema di equazioni con un risolutore di minimi quadrati non lineare utilizzando la piattaforma CUDA. Questi algoritmi devono essere scritti da zero, con l'aiuto di alcune altre librerie che implementano l'algebra lineare con matrici sparse. Inoltre, come menzionato nel commento sopra, la libreria cuBLAS aiuterà con l'algebra lineare.

https://developer.nvidia.com/cusparse

http://code.google.com/p/cusp-library/

Answer 3

Date un'occhiata anche in questo: libflame contiene implementazioni di molte operazioni che vengono forniti dalle BLAS e LAPACK librerie

Answer 4

Per coloro che sono ancora alla ricerca di una risposta, questo è per matrici sparse: di OpenOffice.org, "Quadro per Sparse non lineare dei minimi quadrati Optimization su una GPU"

• https://github.com/OpenOF/OpenOF
• https://www.cv.tu-berlin.de/fileadmin/fg140/OpenOF_01.pdf

È per GPU ciò che g2o è per la CPU.