lemon-project-template-glpk
comparison deps/glpk/src/glpmat.h @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 21:43:29 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a837484d9717 |
---|---|
1 /* glpmat.h (linear algebra routines) */ | |
2 | |
3 /*********************************************************************** | |
4 * This code is part of GLPK (GNU Linear Programming Kit). | |
5 * | |
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, | |
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, | |
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. | |
9 * E-mail: <mao@gnu.org>. | |
10 * | |
11 * GLPK is free software: you can redistribute it and/or modify it | |
12 * under the terms of the GNU General Public License as published by | |
13 * the Free Software Foundation, either version 3 of the License, or | |
14 * (at your option) any later version. | |
15 * | |
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT | |
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
19 * License for more details. | |
20 * | |
21 * You should have received a copy of the GNU General Public License | |
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. | |
23 ***********************************************************************/ | |
24 | |
25 #ifndef GLPMAT_H | |
26 #define GLPMAT_H | |
27 | |
28 /*********************************************************************** | |
29 * FULL-VECTOR STORAGE | |
30 * | |
31 * For a sparse vector x having n elements, ne of which are non-zero, | |
32 * the full-vector storage format uses two arrays x_ind and x_vec, which | |
33 * are set up as follows: | |
34 * | |
35 * x_ind is an integer array of length [1+ne]. Location x_ind[0] is | |
36 * not used, and locations x_ind[1], ..., x_ind[ne] contain indices of | |
37 * non-zero elements in vector x. | |
38 * | |
39 * x_vec is a floating-point array of length [1+n]. Location x_vec[0] | |
40 * is not used, and locations x_vec[1], ..., x_vec[n] contain numeric | |
41 * values of ALL elements in vector x, including its zero elements. | |
42 * | |
43 * Let, for example, the following sparse vector x be given: | |
44 * | |
45 * (0, 1, 0, 0, 2, 3, 0, 4) | |
46 * | |
47 * Then the arrays are: | |
48 * | |
49 * x_ind = { X; 2, 5, 6, 8 } | |
50 * | |
51 * x_vec = { X; 0, 1, 0, 0, 2, 3, 0, 4 } | |
52 * | |
53 * COMPRESSED-VECTOR STORAGE | |
54 * | |
55 * For a sparse vector x having n elements, ne of which are non-zero, | |
56 * the compressed-vector storage format uses two arrays x_ind and x_vec, | |
57 * which are set up as follows: | |
58 * | |
59 * x_ind is an integer array of length [1+ne]. Location x_ind[0] is | |
60 * not used, and locations x_ind[1], ..., x_ind[ne] contain indices of | |
61 * non-zero elements in vector x. | |
62 * | |
63 * x_vec is a floating-point array of length [1+ne]. Location x_vec[0] | |
64 * is not used, and locations x_vec[1], ..., x_vec[ne] contain numeric | |
65 * values of corresponding non-zero elements in vector x. | |
66 * | |
67 * Let, for example, the following sparse vector x be given: | |
68 * | |
69 * (0, 1, 0, 0, 2, 3, 0, 4) | |
70 * | |
71 * Then the arrays are: | |
72 * | |
73 * x_ind = { X; 2, 5, 6, 8 } | |
74 * | |
75 * x_vec = { X; 1, 2, 3, 4 } | |
76 * | |
77 * STORAGE-BY-ROWS | |
78 * | |
79 * For a sparse matrix A, which has m rows, n columns, and ne non-zero | |
80 * elements the storage-by-rows format uses three arrays A_ptr, A_ind, | |
81 * and A_val, which are set up as follows: | |
82 * | |
83 * A_ptr is an integer array of length [1+m+1] also called "row pointer | |
84 * array". It contains the relative starting positions of each row of A | |
85 * in the arrays A_ind and A_val, i.e. element A_ptr[i], 1 <= i <= m, | |
86 * indicates where row i begins in the arrays A_ind and A_val. If all | |
87 * elements in row i are zero, then A_ptr[i] = A_ptr[i+1]. Location | |
88 * A_ptr[0] is not used, location A_ptr[1] must contain 1, and location | |
89 * A_ptr[m+1] must contain ne+1 that indicates the position after the | |
90 * last element in the arrays A_ind and A_val. | |
91 * | |
92 * A_ind is an integer array of length [1+ne]. Location A_ind[0] is not | |
93 * used, and locations A_ind[1], ..., A_ind[ne] contain column indices | |
94 * of (non-zero) elements in matrix A. | |
95 * | |
96 * A_val is a floating-point array of length [1+ne]. Location A_val[0] | |
97 * is not used, and locations A_val[1], ..., A_val[ne] contain numeric | |
98 * values of non-zero elements in matrix A. | |
99 * | |
100 * Non-zero elements of matrix A are stored contiguously, and the rows | |
101 * of matrix A are stored consecutively from 1 to m in the arrays A_ind | |
102 * and A_val. The elements in each row of A may be stored in any order | |
103 * in A_ind and A_val. Note that elements with duplicate column indices | |
104 * are not allowed. | |
105 * | |
106 * Let, for example, the following sparse matrix A be given: | |
107 * | |
108 * | 11 . 13 . . . | | |
109 * | 21 22 . 24 . . | | |
110 * | . 32 33 . . . | | |
111 * | . . 43 44 . 46 | | |
112 * | . . . . . . | | |
113 * | 61 62 . . . 66 | | |
114 * | |
115 * Then the arrays are: | |
116 * | |
117 * A_ptr = { X; 1, 3, 6, 8, 11, 11; 14 } | |
118 * | |
119 * A_ind = { X; 1, 3; 4, 2, 1; 2, 3; 4, 3, 6; 1, 2, 6 } | |
120 * | |
121 * A_val = { X; 11, 13; 24, 22, 21; 32, 33; 44, 43, 46; 61, 62, 66 } | |
122 * | |
123 * PERMUTATION MATRICES | |
124 * | |
125 * Let P be a permutation matrix of the order n. It is represented as | |
126 * an integer array P_per of length [1+n+n] as follows: if p[i,j] = 1, | |
127 * then P_per[i] = j and P_per[n+j] = i. Location P_per[0] is not used. | |
128 * | |
129 * Let A' = P*A. If i-th row of A corresponds to i'-th row of A', then | |
130 * P_per[i'] = i and P_per[n+i] = i'. | |
131 * | |
132 * References: | |
133 * | |
134 * 1. Gustavson F.G. Some basic techniques for solving sparse systems of | |
135 * linear equations. In Rose and Willoughby (1972), pp. 41-52. | |
136 * | |
137 * 2. Basic Linear Algebra Subprograms Technical (BLAST) Forum Standard. | |
138 * University of Tennessee (2001). */ | |
139 | |
140 #define check_fvs _glp_mat_check_fvs | |
141 int check_fvs(int n, int nnz, int ind[], double vec[]); | |
142 /* check sparse vector in full-vector storage format */ | |
143 | |
144 #define check_pattern _glp_mat_check_pattern | |
145 int check_pattern(int m, int n, int A_ptr[], int A_ind[]); | |
146 /* check pattern of sparse matrix */ | |
147 | |
148 #define transpose _glp_mat_transpose | |
149 void transpose(int m, int n, int A_ptr[], int A_ind[], double A_val[], | |
150 int AT_ptr[], int AT_ind[], double AT_val[]); | |
151 /* transpose sparse matrix */ | |
152 | |
153 #define adat_symbolic _glp_mat_adat_symbolic | |
154 int *adat_symbolic(int m, int n, int P_per[], int A_ptr[], int A_ind[], | |
155 int S_ptr[]); | |
156 /* compute S = P*A*D*A'*P' (symbolic phase) */ | |
157 | |
158 #define adat_numeric _glp_mat_adat_numeric | |
159 void adat_numeric(int m, int n, int P_per[], | |
160 int A_ptr[], int A_ind[], double A_val[], double D_diag[], | |
161 int S_ptr[], int S_ind[], double S_val[], double S_diag[]); | |
162 /* compute S = P*A*D*A'*P' (numeric phase) */ | |
163 | |
164 #define min_degree _glp_mat_min_degree | |
165 void min_degree(int n, int A_ptr[], int A_ind[], int P_per[]); | |
166 /* minimum degree ordering */ | |
167 | |
168 #define amd_order1 _glp_mat_amd_order1 | |
169 void amd_order1(int n, int A_ptr[], int A_ind[], int P_per[]); | |
170 /* approximate minimum degree ordering (AMD) */ | |
171 | |
172 #define symamd_ord _glp_mat_symamd_ord | |
173 void symamd_ord(int n, int A_ptr[], int A_ind[], int P_per[]); | |
174 /* approximate minimum degree ordering (SYMAMD) */ | |
175 | |
176 #define chol_symbolic _glp_mat_chol_symbolic | |
177 int *chol_symbolic(int n, int A_ptr[], int A_ind[], int U_ptr[]); | |
178 /* compute Cholesky factorization (symbolic phase) */ | |
179 | |
180 #define chol_numeric _glp_mat_chol_numeric | |
181 int chol_numeric(int n, | |
182 int A_ptr[], int A_ind[], double A_val[], double A_diag[], | |
183 int U_ptr[], int U_ind[], double U_val[], double U_diag[]); | |
184 /* compute Cholesky factorization (numeric phase) */ | |
185 | |
186 #define u_solve _glp_mat_u_solve | |
187 void u_solve(int n, int U_ptr[], int U_ind[], double U_val[], | |
188 double U_diag[], double x[]); | |
189 /* solve upper triangular system U*x = b */ | |
190 | |
191 #define ut_solve _glp_mat_ut_solve | |
192 void ut_solve(int n, int U_ptr[], int U_ind[], double U_val[], | |
193 double U_diag[], double x[]); | |
194 /* solve lower triangular system U'*x = b */ | |
195 | |
196 #endif | |
197 | |
198 /* eof */ |