Åke Björck (akbjo@mai.liu.se)
Mikael Adlers (miadl@mai.liu.se)
Pontus Matstoms (pomat@mai.liu.se)
Purpose
Solution of sparse linear least squares problems.
x=qls(A,b)
x=csne(A,b)
qls and csne solve the least squares problem
![]()
where
,
,
is a sparse matrix of full column rank.
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].
[1] P. Matstoms, Sparse QR factorization in MATLAB, ACM Trans. Math Software, March 1994.
Purpose
Solve sparse least squares with box constraints.
x=sbls(A,b,l,u)
x=sbls(A,b,l,u) solves the constrained sparse linear least squares problem,
![]()
where A is a sparse m -by- n matrix.
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
The solution x is computed by an iterative interior point method, described by [1].
[1] M. Adlers Sparse Least Squares Problems with Box Constraints, Linköping Universitet, Linköping, Sweden
Purpose
Solve sparse least squares with box constraints.
x=sbls2(A,b,l,u)
x=sbls2(A,b,l,u) solves the constrained sparse linear least squares problem,
![]()
![]()
and A is a sparse m -by- n matrix.
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
The solution x is computed by an active set method, described by [1].
[1] M. Adlers Sparse Least Squares Problems with Box Constraints, Linköping Universitet, Linköping, Sweden
Purpose
Generate a sparse least square problem with box constraints.
[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)
[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.
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
The test problem is generated by a generalisation [2] of an algoritm described by Portugal et al. [1].
[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
Purpose
Sparse non-negative least squares.
x=snnls(A,b)
x=snnls(A,b) solves the constrained sparse linear least squares problem,
![]()
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
The solution is computed by the block principal pivoting algorithm, described by Portugal et al. [1].
[1] L. Portugal, J. Júdice, L. Vicente, Solution of large scale linear least-squares problems with nonnegative variables.
Purpose
Sparse QR factorization.
[R,p]=sqr(A)
[R,p,c]=sqr(A,b)
[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.
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.
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.
[1] P. Matstoms, Sparse QR factorization in MATLAB, ACM Trans. Math Software, March 1994.
Purpose
Sparse QR factorization.
[R,p]=sqr2(A)
[R,p,c]=sqr2(A,b)
[R,c,H]=sqr2(A)
[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.
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.
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].
[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.