About this document

Åke Björck (akbjo@mai.liu.se)
Mikael Adlers (miadl@mai.liu.se)
Pontus Matstoms (pomat@mai.liu.se)

qls csne

Purpose

Solution of sparse linear least squares problems.

Synopsis

x=qls(A,b)
x=csne(A,b)

Description

qls and csne solve the least squares problem





where , , is a sparse matrix of full column rank.

Algorithm

Let the QR factorization of A be given by





where is a minimum degree ordering of the columns. qls solves the least squares problem using Golub's method. The solution is computed from Rx=c, .

csne solves the least squares problem using the corrected semi-normal equations, , together with one step of iterative refinement. A comparison of the two methods is carried out in [1].

References

[1] P. Matstoms, Sparse QR factorization in MATLAB, ACM Trans. Math Software, March 1994.

sbls

Purpose

Solve sparse least squares with box constraints.

Synopsis

x=sbls(A,b,l,u)

Description

x=sbls(A,b,l,u) solves the constrained sparse linear least squares problem,





where A is a sparse m -by- n matrix.

Example

Generate a sparse test problem and calculate the relative error of the solution.

>> [A,b,l,u,xexact] = sblsgen (300,50,0.008,1000,0,0,100,100);
>> xpc = sbls (A,b,l,u);                                
>> norm(xexact-xpc)/norm(xexact)

ans =

   1.0050e-08

Algorithm

The solution x is computed by an iterative interior point method, described by [1].

References

[1] M. Adlers Sparse Least Squares Problems with Box Constraints, Linköping Universitet, Linköping, Sweden

sbls2

Purpose

Solve sparse least squares with box constraints.

Synopsis

x=sbls2(A,b,l,u)

Description

x=sbls2(A,b,l,u) solves the constrained sparse linear least squares problem,







and A is a sparse m -by- n matrix.

Example

Generate a sparse test problem and calculate the relative error of the solution.

>> [A,b,l,u,xexact] = sblsgen (300,50,0.008,1000,0,0,100,100);
>> x = sbls2 (A,b,l,u);                                
>> norm(xexact-x)/norm(xexact)

ans =

   8.1505e-17

Algorithm

The solution x is computed by an active set method, described by [1].

References

[1] M. Adlers Sparse Least Squares Problems with Box Constraints, Linköping Universitet, Linköping, Sweden

sblsgen

Purpose

Generate a sparse least square problem with box constraints.

Synopsis

[A,b,l,u,x]=sblsgen(m,n,density,cn,slb,glb,sub,gub)
[A,b,l,u,x]=sblsgen(m,n,density,cn,slb,glb,sub,gub,alpha,nset)

Description

[A,b,l,u,x,w] = sblsgen (m,n,density,cn,slb,glb,sub,gub) generates a random test problem which solves,





[slb,glb] defines the range of the lower bound and [sub,gub] defines the upper bound. nset = [set1,set2,set3,set4,set5] describes the number of variables x who belongs to the following sets; the lower bound and are degenerate, lower bound, upper bound, and are degenerate, upper bound and the free variables. If nset is omitted the sets will have the same size. alpha defines the range of the nonzero complementary variables [-alpha,alpha]. If alpha is omitted it is set to 100.

Example

Generate a sparse test problem and calculate the relative error of the solution.

>> [A,b,l,u,xexact]=sblsgen(300,50,0.008,1e3,0,5,10,200,...
                            1e2,10*[1 1 1 1 1]);
>> xpc = sbls(A,b,u,l);                                
>> norm(xexact-xpc)/norm(xexact)

ans =

   1.1013e-07

Algorithm

The test problem is generated by a generalisation [2] of an algoritm described by Portugal et al. [1].

References

[1] L. Portugal, J. Júdice, L. Vicente, Solution of large scale linear least-squares problems with nonnegative variables.

[2] M. Adlers Sparse Least Squares Problems with Box Constraints, Linköping Universitet, Linköping, Sweden

See also sbls, snnls.

snnls

Purpose

Sparse non-negative least squares.

Synopsis

x=snnls(A,b)

Description

x=snnls(A,b) solves the constrained sparse linear least squares problem,

Example

Load a sparse matrix from the library and generate a least squares problem with the exact solution :

load('abb313');
x=-ones(size(A,2),1);
b=A*x;

The non-negative least squares solution and the corresponding residual are then obtained by:

>> xx=snnls(A,b);
>> norm(b-A*xx)

ans =

   22.1893

Algorithm

The solution is computed by the block principal pivoting algorithm, described by Portugal et al. [1].

References

[1] L. Portugal, J. Júdice, L. Vicente, Solution of large scale linear least-squares problems with nonnegative variables.

See also nnls

sqr

Purpose

Sparse QR factorization.

Synopsis

[R,p]=sqr(A)
[R,p,c]=sqr(A,b)

Description

[R,p]=sqr(A) computes the upper triangular matrix R in the QR factorization of the sparse matrix A(r,p),



Here, p is a postordered column ordering and r the row ordering used. Since R is invariant under row orderings of A, r is not made available for the user.

[R,p,c]=sqr(A,b) does also compute the n first components of . This vector/matrix is often used in the solution of sparse linear least squares problems.

Example

Sparse linear least squares problems, , are easily solved by the use of sqr. A fill-in minimizing column ordering q is first computed. Then the resulting matrix is factorized and the least squares solution computed from the triangular system . Since sqr computes the QR factorization of a column permutation of A, the inverse ordering must be applied to the computed solution.

q=colmmd(A);            % Minimum degree ordering of A.
[R,p,c]=sqr(A(:,q),b);  % Sparse QR-factorization.
Pc=q(p);                % Resulting column permutation.
x=R\c;                  % Least squares solution
x(Pc)=x;                % Permute the solution.

Algorithm

The upper triangular matrix R is computed by a multifrontal scheme described by Matstoms [1]. For each node in the elimination tree of , a dense frontal matrix is formed and factorized. The first rows of the factor define one or more rows of R, and the remaining part forms an update matrix to be included in the frontal matrix of the father node.

References

[1] P. Matstoms, Sparse QR factorization in MATLAB, ACM Trans. Math Software, March 1994.

sqr2

Purpose

Sparse QR factorization.

Synopsis

[R,p]=sqr2(A)
[R,p,c]=sqr2(A,b)
[R,c,H]=sqr2(A)

Description

[R,p]=sqr(A) computes the upper triangular matrix R in the QR factorization of the sparse matrix A(r,p),



Here, p is a postordered column ordering and r the row ordering used. Since R is invariant under row orderings of A, r is not made available for the user.

[R,p,c]=sqr(A,b) does also compute the n first components of . This vector/matrix is often used in the solution of sparse linear least squares problems.

[R,c,H]=sqr2(A) computes a sparse representation H of the orthogonal factor. H is stored as a new data type, sparseQ. This matrix can be used a an ordinaru matrix.

Example

Sparse linear least squares problems, , are easily solved by the use of sqr. A fill-in minimizing column ordering q is first computed. Then the resulting matrix is factorized and the least squares solution computed from the triangular system . Since sqr computes the QR factorization of a column permutation of A, the inverse ordering must be applied to the computed solution.

q=colmmd(A);            % Minimum degree ordering of A.
[R,p,H]=sqr2(A(:,q));   % Sparse QR-factorization.
Pc=q(p);                % Resulting column permutation.
c=H'*b;                 % Apply orthogonal matrix
x=R\c(1:size(A,2));     % Least squares solution
x(Pc)=x;                % Permute the solution.

Algorithm

The upper triangular matrix R is computed by a multifrontal scheme described by Matstoms [1]. For each node in the elimination tree of , a dense frontal matrix is formed and factorized. The first rows of the factor define one or more rows of R, and the remaining part forms an update matrix to be included in the frontal matrix of the father node. The orthogonal factor is computed as described in Adlers [2].

References

[1] P. Matstoms, Sparse QR factorization in MATLAB, ACM Trans. Math Software, March 1994.

[2] M. Adlers Computing sparse orthogonal factor in MATLAB, Techical report LiTH-MAT-R-98-19, Linköpings Universitet.

About this document ...