## Linear Least-square solvers

Post here if you have a question about LAPACK or ScaLAPACK algorithm or data format

### Linear Least-square solvers

Hi everyone,

I am fairly new here, and this post may or may not be in the right section. I apologize if it's not where it's supposed to be.

In my work I need to solve a linear least square unconstrained problem. I found three LAPACK routines that can be useful :
Code: Select all
`SGELS(..)SGELSD(..)SGELSY(..)`

I compared them in terms of precision and execution time, and it allowed me to choose one, but now i am looking for a more in depth understanding.

Can any one explain me the differences between these methods?

Thanks
A.
anslab

Posts: 4
Joined: Sat May 07, 2011 4:18 am

### Re: Linear Least-square solvers

Did you take a look at the LAPACK user guide?
http://www.netlib.org/lapack/lug/node1.html
Julie
admin
Site Admin

Posts: 612
Joined: Wed Dec 08, 2004 7:07 pm

### Re: Linear Least-square solvers

Yes I did, I also browsed the sources of the aforementionned functions, but I must admit I'm still in the dark. I also asked my good friend wikipedia, but he wasn't of much help. Maybe you can point me to a paper or any other good ressource?
anslab

Posts: 4
Joined: Sat May 07, 2011 4:18 am

### Re: Linear Least-square solvers

* xGELS solves the linear least squares problem using a QR factorization.
* xGELSY solves the linear least squares problem using a QR factorization with column pivoting.
* xGELSD solves the linear least squares problem using the singular value decompostion.

In term of speed, you should get xGELS faster than xGELSY faster than xGELSD.
In term of functionality, xGELS only handles nonsingular matrices, xGELSY and xGELSD handles any matrix. xGELSY might have some problems for some pathological matrices. xGELSD works for all matrices.

J
Julien Langou

Posts: 827
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

### Re: Linear Least-square solvers

Okay,

When i did some testing, i noticed that there is a discrepancy in precision, i.e. xGELSD seems to find a more accurate solution than the other two. Is there any theoretical explanation, or is it implementation-related?
anslab

Posts: 4
Joined: Sat May 07, 2011 4:18 am

### Re: Linear Least-square solvers

1) What do you mean by "xGELSD seems to find a more accurate solution than the other two"? Measuring the "accuracy" of a linear least squares solver is tricky ... Do you check which one has the smallest 2-norm residual ( || b - A x || )? Do you check which one has the most orthogonal residual (i.e. smallest A^T (b- Ax ) ) ? I assume the first. (Which is fine.)

2) In term of accuracy, you should expect xGELSD to be better than the two other two when the problem becomes ill-conditionned. (The order should actually be: xGELS is the worse, xGELSY should come second, then xGELSD.) Of course there is a price (i.e., time) to this improved accuracy. In term of time, you should expect the reverse order.

Cheers,
Julien.
Julien Langou

Posts: 827
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

### Re: Linear Least-square solvers

1) Yes, i did the first solution. I generated a bunch of system from a given solution in order to measure the accuracy (in the 2-norm sense) and the execution time.

What I need to understand now is, why xGELSD is more accurate that the other on the same problem than the other solvers?

Thanks for taking the time to answers my questions, I think you just earned a line of thanks in my PhD.
anslab

Posts: 4
Joined: Sat May 07, 2011 4:18 am

Return to Algorithm / Data

### Who is online

Users browsing this forum: No registered users and 1 guest