Risoluzione di sistemi lineari di equazioni

Ho un sistema di 6 equazioni che ho bisogno di risolvere più e più volte in un programma (con molti ingressi diversi ovviamente). Attualmente sto usando il metodo della regola di Cramer per risolvere il sistema e funziona abbastanza bene (sembra che al mio processore piaccia davvero aggiungere e moltiplicare le operazioni, ottiene soluzioni in 1 microsecondo nonostante le equazioni esplicite siano più lunghe di 2 pagine). Tuttavia il numero di volte che ho bisogno di risolvere è enorme e sto cercando un metodo ancora più veloce.Risoluzione di sistemi lineari di equazioni

La domanda è: esiste un metodo ancora più veloce o più efficiente per risolvere queste equazioni o qualcosa di simile al CUDA può essere utile qui?

fonte

2010-07-24 Faken

Sei sicuro che tutte e 6 le equazioni sono necessarie? Le equazioni sono state ridotte il più possibile? – BoltBait

Sto risolvendo un problema di stabilità, richiede 6 DOF (3 forze xyz ortogonali e 3 coppie xyz). Ho ricavato le equazioni da MATLAB e ho codificato in modo rigido le soluzioni esplicite nel programma (con la determinazione che viene risolta separatamente).Tuttavia, non c'è modo che io possa semplificare ulteriormente le equazioni attuali, sono troppo grandi e ingombranti. – Faken

Come calcolate i fattori determinanti? – sellibitze

forse si potrebbe dare http://arma.sourceforge.net/docs.html una prova.

Fornisce la funzione di risoluzione pre-ordine, http://arma.sourceforge.net/docs.html#solve. tuttavia usa il backand di atlante/lapack, che è orientato più verso funzioni più grandi.

Puoi anche provare la moltiplicazione per inverso, http://arma.sourceforge.net/docs.html#inv, che è un modello di tempo di compilazione e forse più veloce per i tuoi scopi.

provare questo: x = inv (A) * b. Poiché A non cambia, l'inversione viene eseguita una sola volta. Allora sei a casa libera con moltiplicazioni vettoriali a matrice semplice, che saranno veramente veloci

fonte

2010-07-24 05:06:27 Anycorn

@GMan rimosso. In altre note, sto lavorando su cublas/ublas bridge e cerco partner. conosci qualcuno (o te stesso) che potrebbe essere interessato? Penso di aver visto da qualche parte che hai menzionato usando cuda – Anycorn

@aaa: vuoi dire consentire agli uBLAS di Boost (o qualche altra libreria BLAS) di sfruttare CUBLAS? Sono interessato, di per sé, ma non ho tempo per lavorare su nient'altro. :(Ho davvero usato CUDA, ma solo per curiosare, non ho mai fatto nulla di serio con questo – GManNickG

@GMan sicuro, nessun problema.Ho pensato che potresti aver conosciuto qualcuno .. è più come avere le espressioni ublas ma in GPU memoria che utilizza kernel cubani e poche funzioni per comunicare: qui è un piccolo test case: http://code.google.com/p/asadchev/source/browse/trunk/projects/boost/numeric/bindings/cublas/test.cpp – Anycorn

Si potrebbe verificare .

Il metodo non è così semplice, tuttavia; ti consigliamo di esaminare LU decomposition.

fonte

2010-07-24 04:29:02 GManNickG

o qualsiasi altra libreria che offre cose come decomposizione LU, sostituzione avanti/indietro (+1) – sellibitze

La decomposizione LU è un metodo semplice da usare per risolvere le cose? Ho programmato uno di quegli algoritmi anni fa con la mia calcolatrice TI-83 mentre ero terribilmente annoiato nella classe dei metodi numerici, come ho ricordato, ha usato molte divisioni, anche se non è molto facile da usare. Darò di nuovo un'occhiata, forse posso ricavare alcune equazioni generali sul codice nel programma. – Faken

@aaa: la "forma" delle mie equazioni è nota e non cambia, solo i valori sono diversi (ci sono anche zero e uno nella matrice quando sono formati in una forma utilizzabile dalla regola di Cramer). l'uBLAS non prenderà in considerazione ciò, vero? – Faken

È possibile ottenere almeno un raddoppio utilizzando SSE2 o versione successiva. Ma questo impallidirebbe rispetto a una porta CUDA o OpenCL, che, se fatto bene, potrebbe produrre un'accelerazione di uno o due ordini di grandezza.

Se si conosce Python, PyCUDA potrebbe essere un buon punto di ingresso.

fonte

2010-07-24 04:37:14

Attualmente sto usando VS2008 su un processore core i7, SSE2 sarebbe già abilitato di default? In caso contrario, come posso abilitarlo? Inoltre, concettualmente, quale sarebbe il modo migliore per implementare CUDA su un livello molto alto (come un thread per generare valori da calcolare, un thread per gestire il caricamento e il recupero dei dati da CUDA e uno per l'elaborazione dei risultati, ect)? – Faken

Definitivamente. SSE2 è stato introdotto quasi dieci anni fa. L'architettura Core i7 supporta [SSE4.2] (http://en.wikipedia.org/wiki/SSE4). Non posso aiutarti su CUDA, temo, non ci gioco molto. –

La regola di Cramer non si adatta bene. Per un piccolo sistema di equazioni con due o tre incognite va bene, ma se il sistema diventa più grande, altri metodi sono più efficienti, ad esempio: decomposizione LU + sostituzione diretta + sostituzione all'indietro.

fonte

2010-07-24 04:51:16 sellibitze

Sì, lo so ... le equazioni sono enormi. Dò un'occhiata a LU. Secondo te, dovrei considerare l'utilizzo di una libreria generale per risolverli o dovrei limitarmi a cercare metodi più efficaci per i metodi matematici, in quanto conosco i dettagli sulla forma esatta del sistema di equazioni? – Faken

LU funziona se si risolve un sistema Ab = y, più volte. La prima corsa è costosa, le corse successive sono veloci. – joel3000

Se si desidera eseguire CUDA, è necessario una scheda grafica discreta Nvidia

Se si dispone di una CPU Intel, io recommanded si utilizza Intel MKL http://software.intel.com/en-us/intel-mkl/, che è ottimizzato per CPU Intel,

Se si utilizza CUDA, si potrebbe avere problemi con float o doppia precisione questione

Inoltre, se non si ha familiarità con la programmazione della GPU, si sono gonna passare più tempo sulla soluzione CUDA

fonte

2010-07-24 05:02:58 shader

Aww ... $ 400+ sì, questo è fuori dal mio budget operativo. Forse la mia università ha delle licenze, pensavo che avrebbe escluso di poter lavorare da casa. Sono a conoscenza del singolo/doppio problema con CUDA, attualmente sto usando il doppio semplicemente perché non prendo alcuna penalità di velocità a causa di esso. Tuttavia, se uso la regola di Cramer, dovrei riuscire a farla franca con un singolo punto a causa della mancanza di divisioni. – Faken

@Fake, l'addizione e la sottrazione sono la principale fonte di errore. Moltiplicazione e divisione non tanto – Anycorn

@shader: Heh, è sporco ... – Faken

A meno che tu non possa risolvere la tua equazione in ordine non sequenziale, CUDA non ti aiuterà. In effetti, CUDA potrebbe essere più lento. Tutto ciò che non è imbarazzante parallelo non trarrà beneficio da CUDA. Abilitare SSE2 tramite l'interruttore del compilatore non è sufficiente. Hai bisogno di una libreria che è codificata per utilizzare SSE2. A mio parere, la migliore libreria di algebra lineare è Eigen. È molto facile da usare e supporta SIMD (non solo SSE2).

fonte

2010-07-26 13:47:59 user401947

Cosa intendi risolvendo le equazioni in ordine non sequenziale? Ora so che questo problema è in realtà un problema di ottimizzazione multi-variabile (per quanto riguarda l'apprendimento, il progetto ha l'abitudine di farlo per me). Tuttavia è un problema di ottimizzazione all'interno di un problema di ottimizzazione, quindi posso parallelizzare i singoli problemi di ottimizzazione. Se avessi la CPU principale per impostare i problemi, CUDA sarebbe in grado di regolare i parametri e fare iterazioni senza essere esplicitamente alimentato dai dati dalla CPU? Al contrario della CPU che prepara una matrice e CUDA risolvendolo e semplicemente restituendolo, nient'altro? – Faken

Pensa alla GPU come a un processore multicore. La GPU ha molti core, ma ogni core è molto più debole del core della CPU. GPU ha la sua forza dalla parallelizzazione. Puoi dividere l'intero problema in sotto-attività che possono essere eseguite in modo interdipendente? Di ', hai equazioni 1, 2, ..., N. Puoi risolverli in modo indipendente? Se è così, CUDA può aiutare. Potresti provare a mettere in parallelo il tuo codice sulla CPU, perché fare lo stesso con CUDA è più difficile. Nella mia esperienza, l'algebra lineare è notoriamente difficile da parallelizzare, a meno che, ovviamente, il problema non sia costituito da sub-compiti indipendenti. – user401947

CUDA è un linguaggio di programmazione simile a C. La codifica GPU implica una gestione esplicita della memoria. Devi stare molto attento a spostare i dati in giro. Risolvere un'equazione 6x6 e restituire la risposta alla CPU non giustifica il sovraccarico. Per beneficiare della GPU, il tuo algoritmo deve essere in grado di semplificare un numero molto grande di equazioni contemporaneamente. Non ci dovrebbe essere alcuna dipendenza tra equazioni semplificate. Quindi la GPU può risolvere tutte queste equazioni più velocemente della CPU. – user401947

Risoluzione di sistemi lineari di equazioni

risposta

Problemi correlati