Risolvendo normale sistema di equazioni in C++

desidero risolvere il sistema di equazioni lineari:Risolvendo normale sistema di equazioni in C++

Ax = b

A è una matrice n x m (non quadrata), b ed x sono entrambi n x 1 vettori. Dove A e b sono noti, n è dell'ordine di 50-100 e m è di circa 2 (in altre parole, A potrebbe essere massimo [100x2]).

So che la soluzione di x: $x = \inv(A^T A) A^T b$

ho trovato alcuni modi per risolverlo: uBLAS (Boost), LAPACK, Eigen ed ecc ma non so quanto velocemente sono il tempo di calcolo della CPU di 'x' usando quei pacchetti. Inoltre, non so se questo numericamente un veloce perché risolvere 'x'

Ciò che è importante per me è che il tempo di calcolo della CPU sarebbe il più breve possibile e una buona documentazione poiché sono novellino.

Dopo aver risolto l'equazione normale Ax = b vorrei migliorare la mia approssimazione utilizzando regressivo e forse successivo applicando Filtro Kalman.

La mia domanda è quale libreria C++ è la robusta e più veloce per le esigenze che ho descritto sopra?

fonte

2011-01-03 Eagle

Come si fa a più di un m n x matrice da un n dimensionale vettore colonna? Presumibilmente x è in realtà m dimensionale. –

Inoltre, hai qualche requisito che stabilisce una quantità minima di conformità di buzzword? –

@Eagle Non penso che la libreria Boost di uBLAS implementa questo, ma per favore correggimi se sbaglio. Sembra piuttosto che uBLAS fornisca vettori, matrici e operazioni di base (moltiplicazione, aggiunta) ma nulla come LU, QR, SVD o inversione di matrici, per non parlare dell'implementazione di OLS. Tuttavia è probabilmente una buona libreria per implementare tali algoritmi. Ancora una volta, per favore dimmi se ho torto o se trovi un'implementazione Boost uBLAS OLOS ... – Arthur

Questa è una soluzione per i minimi quadrati, perché si hanno più incognite che equazioni: se m è effettivamente uguale a 2, questo mi dice che un semplice quadratino lineare lineare sarà sufficiente per te. Le formule possono essere scritte in forma chiusa. Non è necessaria una libreria.

Se m è in cifre singole, direi che è possibile risolverlo facilmente utilizzando A (trasposizione) * A * X = A (trasposizione) * b. Una semplice decomposizione LU da risolvere per i coefficienti sarebbe sufficiente.Dovrebbe essere un problema molto più diretto di quello che stai cercando di essere.

fonte

2011-01-03 14:17:26 duffymo

+1 per i minimi quadrati. –

Parla del filtro di Kalman. Presumo che stia bene con l'algebra lineare e OLS in particolare. Vuole libreria ottimizzata. – watson1180

@duffymo, hai ragione, per ora la soluzione di $ x = \ inv (A^T A) A^T b $ è quello che sto cercando. Il filtro Kalman è forse per lo sviluppo futuro. Quello che per me era importante è quale libreria (che supporti inversione, trasposizione, moltiplicazione della matrice e così via) dovrei lavorare con (Boost, Eigen, Lapack o ecc.) – Eagle

Se si ha accesso a MATLAB, si consiglia di utilizzare le sue librerie C.

fonte

2011-01-03 13:42:30 swegi

hmm, piuttosto un soluzione brutale a un problema banale! –

AFAIK, la libreria Matlab C (almeno le routine di algebra lineare) usano/basano alcune delle librerie note pubblicamente conosciute (LAPACK). – watson1180

@watson tutte le librerie di algebra lineare sono essenzialmente le stesse e derivano dal manuale –

uBlas non è ottimizzato a meno che non lo si utilizzi con associazioni BLAS ottimizzate.

Le seguenti sono ottimizzati per il multi-thread e SIMD:

Intel MKL. Libreria FORTRAN con interfaccia C. Non libero ma molto buono.
Eigen. Vera libreria C++. Gratuito e open source. Facile da usare e buono.
Atlas. FORTRAN e C. Libero e open source. Non adatto a Windows, ma per il resto buono.

Btw, non so esattamente cosa stai facendo, ma di norma le equazioni normali non sono un modo corretto di fare regressione lineare. A meno che la matrice non sia ben condizionata, è preferibile utilizzare QR o SVD.

fonte

2011-01-03 14:04:37 watson1180

Anche ACML per chip AMD. Questo è gratuito, credo. – Tom

Non sono sicuro che le versioni ottimizzate mult-threaded rappresenterebbero un vantaggio per le matrici tanto minuscolo come questo. –

incrementerebbe :: numeric :: ublas essere considerato come "binding ottimizzato BLAS"? – Eagle

Se liscencing non è un problema, si potrebbe provare la GNU biblioteca scientifica

http://www.gnu.org/software/gsl/

Esso viene fornito con una libreria Blas che si può scambiare per una libreria ottimizzata se avete bisogno di un secondo momento (ad esempio, la libreria intel, ATLAS o ACML (AMD chip)

fonte

2011-01-03 14:14:29 Tom

Le routine di algebra lineare GSL non sono ottimizzate. – watson1180

@watson quindi, non è necessario ottimizzare l'immaginazione per 100x2? –

@watson Fornisce comunque un'interfaccia alla libreria BLAS sottostante? Puoi scambiare la tua libreria BLAS preferita in collegamento anziché in codice se trovi che devi davvero ottimizzare – Tom

-1

Se è davvero necessario specializzarsi, è possibile approssimare l'inversione della matrice (con precisione arbitraria) utilizzando il metodo Skilling. Usa solo le operazioni di ordine (N^2) (piuttosto che l'ordine N^3 della normale inversione di matrice - decomposizione LU ecc.).

sua descritti nella tesi di Gibbs legati a qui (circa pagina 27):

http://www.inference.phy.cam.ac.uk/mng10/GP/thesis.ps.gz

fonte

2011-01-03 14:24:32 Tom

Non utilizzare mai l'inversione della matrice per risolvere sistemi lineari. La risoluzione dei sistemi lineari è essenzialmente un problema di O (n^2). –

@Alexandre Davvero? - Sarei interessato alla tua soluzione. La scomposizione di LU, ad esempio, è Order N^3 (secondo la tesi che cito, comunque). – Tom

@Alexandre Non penso che il grande O sia molto rilevante per piccoli problemi come questo .... –

Risolvendo normale sistema di equazioni in C++

risposta

Problemi correlati