COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpmat.h @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 7.3 KB
Line 
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 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
141int 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
145int 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
149void 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
154int *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
159void 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
165void 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
169void 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
173void 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
177int *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
181int 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
187void 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
192void 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 */
Note: See TracBrowser for help on using the repository browser.