1 | /* $Id: ClpLsqr.hpp 1502 2010-01-29 14:25:07Z forrest $ */ |
---|
2 | // Copyright (C) 2003, International Business Machines |
---|
3 | // Corporation and others. All Rights Reserved. |
---|
4 | #ifndef ClpLsqr_H_ |
---|
5 | #define ClpLsqr_H_ |
---|
6 | |
---|
7 | #include "CoinDenseVector.hpp" |
---|
8 | |
---|
9 | #include "ClpInterior.hpp" |
---|
10 | |
---|
11 | |
---|
12 | /** |
---|
13 | This class implements LSQR |
---|
14 | |
---|
15 | @verbatim |
---|
16 | LSQR solves Ax = b or min ||b - Ax||_2 if damp = 0, |
---|
17 | or min || (b) - ( A )x || otherwise. |
---|
18 | || (0) (damp I) ||2 |
---|
19 | A is an m by n matrix defined by user provided routines |
---|
20 | matVecMult(mode, y, x) |
---|
21 | which performs the matrix-vector operations where y and x |
---|
22 | are references or pointers to CoinDenseVector objects. |
---|
23 | If mode = 1, matVecMult must return y = Ax without altering x. |
---|
24 | If mode = 2, matVecMult must return y = A'x without altering x. |
---|
25 | |
---|
26 | ----------------------------------------------------------------------- |
---|
27 | LSQR uses an iterative (conjugate-gradient-like) method. |
---|
28 | For further information, see |
---|
29 | 1. C. C. Paige and M. A. Saunders (1982a). |
---|
30 | LSQR: An algorithm for sparse linear equations and sparse least squares, |
---|
31 | ACM TOMS 8(1), 43-71. |
---|
32 | 2. C. C. Paige and M. A. Saunders (1982b). |
---|
33 | Algorithm 583. LSQR: Sparse linear equations and least squares problems, |
---|
34 | ACM TOMS 8(2), 195-209. |
---|
35 | 3. M. A. Saunders (1995). Solution of sparse rectangular systems using |
---|
36 | LSQR and CRAIG, BIT 35, 588-604. |
---|
37 | |
---|
38 | Input parameters: |
---|
39 | |
---|
40 | atol, btol are stopping tolerances. If both are 1.0e-9 (say), |
---|
41 | the final residual norm should be accurate to about 9 digits. |
---|
42 | (The final x will usually have fewer correct digits, |
---|
43 | depending on cond(A) and the size of damp.) |
---|
44 | conlim is also a stopping tolerance. lsqr terminates if an estimate |
---|
45 | of cond(A) exceeds conlim. For compatible systems Ax = b, |
---|
46 | conlim could be as large as 1.0e+12 (say). For least-squares |
---|
47 | problems, conlim should be less than 1.0e+8. |
---|
48 | Maximum precision can be obtained by setting |
---|
49 | atol = btol = conlim = zero, but the number of iterations |
---|
50 | may then be excessive. |
---|
51 | itnlim is an explicit limit on iterations (for safety). |
---|
52 | show = 1 gives an iteration log, |
---|
53 | show = 0 suppresses output. |
---|
54 | info is a structure special to pdco.m, used to test if |
---|
55 | was small enough, and continuing if necessary with smaller atol. |
---|
56 | |
---|
57 | |
---|
58 | Output parameters: |
---|
59 | x is the final solution. |
---|
60 | *istop gives the reason for termination. |
---|
61 | *istop = 1 means x is an approximate solution to Ax = b. |
---|
62 | = 2 means x approximately solves the least-squares problem. |
---|
63 | rnorm = norm(r) if damp = 0, where r = b - Ax, |
---|
64 | = sqrt( norm(r)**2 + damp**2 * norm(x)**2 ) otherwise. |
---|
65 | xnorm = norm(x). |
---|
66 | var estimates diag( inv(A'A) ). Omitted in this special version. |
---|
67 | outfo is a structure special to pdco.m, returning information |
---|
68 | about whether atol had to be reduced. |
---|
69 | |
---|
70 | Other potential output parameters: |
---|
71 | anorm, acond, arnorm, xnorm |
---|
72 | @endverbatim |
---|
73 | */ |
---|
74 | class ClpLsqr { |
---|
75 | private: |
---|
76 | /**@name Private member data */ |
---|
77 | //@{ |
---|
78 | //@} |
---|
79 | |
---|
80 | public: |
---|
81 | /**@name Public member data */ |
---|
82 | //@{ |
---|
83 | /// Row dimension of matrix |
---|
84 | int nrows_; |
---|
85 | /// Column dimension of matrix |
---|
86 | int ncols_; |
---|
87 | /// Pointer to Model object for this instance |
---|
88 | ClpInterior *model_; |
---|
89 | /// Diagonal array 1 |
---|
90 | double *diag1_; |
---|
91 | /// Constant diagonal 2 |
---|
92 | double diag2_; |
---|
93 | //@} |
---|
94 | |
---|
95 | /**@name Constructors and destructors */ |
---|
96 | /** Default constructor */ |
---|
97 | ClpLsqr(); |
---|
98 | |
---|
99 | /** Constructor for use with Pdco model (note modified for pdco!!!!) */ |
---|
100 | ClpLsqr(ClpInterior *model); |
---|
101 | /// Copy constructor |
---|
102 | ClpLsqr(const ClpLsqr &); |
---|
103 | /// Assignment operator. This copies the data |
---|
104 | ClpLsqr & operator=(const ClpLsqr & rhs); |
---|
105 | /** Destructor */ |
---|
106 | ~ClpLsqr(); |
---|
107 | //@} |
---|
108 | |
---|
109 | /**@name Methods */ |
---|
110 | //@{ |
---|
111 | /// Set an int parameter |
---|
112 | bool setParam(char *parmName, int parmValue); |
---|
113 | /// Call the Lsqr algorithm |
---|
114 | void do_lsqr( CoinDenseVector<double> &b, |
---|
115 | double damp, double atol, double btol, double conlim, int itnlim, |
---|
116 | bool show, Info info, CoinDenseVector<double> &x , int *istop, |
---|
117 | int *itn, Outfo *outfo, bool precon, CoinDenseVector<double> &Pr ); |
---|
118 | /// Matrix-vector multiply - implemented by user |
---|
119 | void matVecMult( int, CoinDenseVector<double> *, CoinDenseVector<double> *); |
---|
120 | |
---|
121 | void matVecMult( int, CoinDenseVector<double> &, CoinDenseVector<double> &); |
---|
122 | /// diag1 - we just borrow as it is part of a CoinDenseVector<double> |
---|
123 | void borrowDiag1(double * array) { |
---|
124 | diag1_ = array; |
---|
125 | }; |
---|
126 | //@} |
---|
127 | }; |
---|
128 | #endif |
---|
129 | |
---|
130 | |
---|
131 | |
---|
132 | |
---|