Geek Answers Handbook

Solving a normal system of equations in C ++

I would like to solve a system of linear equations:

Ax = b

A is the matrix nxm (not square), b and x are the vectors nx 1 . Where A and b are known, n is of the order of 50-100, and m is 2 (in other words, A can be maximum [100x2]).

I know the solution x : $x = \inv(A^TA) A^T b$

I found several ways to solve this problem: uBLAS (Boost), Lapack, Eigen, etc., but I don’t know how fast the processor time calculation of “x” is calculated using these packages. I also don't know if it was numerically fast, why solve the "x"

What is important to me is that the computation time of the processor will be as short as possible, and good documentation, since I'm a beginner.

After solving the normal equation Ax = b I would like to improve my approximation using regressive and , possibly, later , applying the Kalman filter.

My question is, which C ++ library is a robot and faster for the needs described above?

+7
source share
5 answers

This is the least squares solution because you have more unknowns than equations. If m is really 2, this tells me that simple linear least squares will suffice for you. Formulas can be written in closed form. You do not need a library.

If m is clear, I would say that you can easily solve this using A (transpose) * A * X = A (transpose) * b. A simple decomposition of LU is enough to solve for the coefficients. This should be a much simpler problem than you do.

+7
source

uBlas is not optimized unless you use it with optimized BLAS bindings.

The following are optimized for multithreading and SIMD:

  • Intel MKL. FORTRAN library with C interface. Not free, but very good.
  • Eigen. True C ++ Library. Free and open source. Easy to use and good.
  • Atlas. FORTRAN and C. Free and open source. Not Windows friendly, but otherwise good.

Btw, I don’t know exactly what you are doing, but as a rule, normal equations are not the proper way to perform linear regression. If your matrix is ​​well-conditioned, it is advisable that QR or SVD be preferred.

+7
source

If collecting information is not a problem, you can try the gnu science library

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

It comes with a blas library, which you can exchange for an optimized library if you need later (for example, Intel, ATLAS or ACML (AMD).

+2
source

If you have access to MATLAB, I would recommend using its C libraries.

+1
source

If you really need to specialize, you can approximate the inverse of the matrix (arbitrary precision) using the Skilling method. It uses only operations of order (N ^ 2) (and not order N ^ 3 of the usual matrix inversion - decomposition LU, etc.)

Described in the Gibbs thesis linked here (about page 27):

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

-one
source

More articles:


All Articles