Code_Saturne
CFD tool
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
fvm_hilbert.h
Go to the documentation of this file.
1 #ifndef __FVM_HILBERT_H__
2 #define __FVM_HILBERT_H__
3 
4 /*============================================================================
5  * Hilbert space-filling curve construction for coordinates.
6  *============================================================================*/
7 
8 /*
9  This file is part of Code_Saturne, a general-purpose CFD tool.
10 
11  Copyright (C) 1998-2012 EDF S.A.
12 
13  This program is free software; you can redistribute it and/or modify it under
14  the terms of the GNU General Public License as published by the Free Software
15  Foundation; either version 2 of the License, or (at your option) any later
16  version.
17 
18  This program is distributed in the hope that it will be useful, but WITHOUT
19  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20  FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
21  details.
22 
23  You should have received a copy of the GNU General Public License along with
24  this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
25  Street, Fifth Floor, Boston, MA 02110-1301, USA.
26 */
27 
28 /*----------------------------------------------------------------------------*/
29 
30 #if defined(HAVE_MPI)
31 #include <mpi.h>
32 #endif
33 
34 /*----------------------------------------------------------------------------
35  * Local headers
36  *----------------------------------------------------------------------------*/
37 
38 #include "fvm_defs.h"
39 
40 /*----------------------------------------------------------------------------*/
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #if 0
45 } /* Fake brace to */
46 #endif
47 #endif /* __cplusplus */
48 
49 /*============================================================================
50  * Macro and type definitions
51  *============================================================================*/
52 
53 /* Hilbert code
54  (could be switched from double to long double for extened range) */
55 
56 typedef double fvm_hilbert_code_t;
57 
58 /*============================================================================
59  * Public function definitions
60  *============================================================================*/
61 
62 /*----------------------------------------------------------------------------
63  * Determine the global extents associated with a set of coordinates
64  *
65  * parameters:
66  * dim <-- spatial dimension
67  * n_coords <-- local number of coordinates
68  * coords <-- entity coordinates; size: n_entities*dim (interlaced)
69  * g_extents --> global extents (size: dim*2)
70  * comm <-- associated MPI communicator
71  *---------------------------------------------------------------------------*/
72 
73 #if defined(HAVE_MPI)
74 void
76  size_t n_coords,
77  const cs_coord_t coords[],
78  cs_coord_t g_extents[],
79  MPI_Comm comm);
80 #else
81 void
83  size_t n_coords,
84  const cs_coord_t coords[],
85  cs_coord_t g_extents[]);
86 #endif
87 
88 /*----------------------------------------------------------------------------
89  * Encode an array of coordinates.
90  *
91  * The caller is responsible for freeing the returned array once it is
92  * no longer useful.
93  *
94  * parameters:
95  * dim <-- 1D, 2D or 3D
96  * extents <-- coordinate extents for normalization (size: dim*2)
97  * n_coords <-- nomber of coordinates in array
98  * coords <-- coordinates in the grid (interlaced, not normalized)
99  * h_code --> array of corresponding Hilbert codes (size: n_coords)
100  *----------------------------------------------------------------------------*/
101 
102 void
104  const cs_coord_t extents[],
105  cs_lnum_t n_coords,
106  const cs_coord_t coords[],
107  fvm_hilbert_code_t h_code[]);
108 
109 /*----------------------------------------------------------------------------
110  * Locally order a list of Hilbert ids.
111  *
112  * This variant uses an encoding into floating-point numbers. In 3D, this
113  * limits us to 19 levels for a double, though using a long double could
114  * increase this range.
115  *
116  * parameters:
117  * n_codes <-- number of Hilbert ids to order
118  * hilbert_codes <-- array of Hilbert ids to order
119  * order --> pointer to pre-allocated ordering table
120  *----------------------------------------------------------------------------*/
121 
122 void
124  const fvm_hilbert_code_t hilbert_codes[],
125  cs_lnum_t order[]);
126 
127 /*----------------------------------------------------------------------------
128  * Locally order a list of coordinates based on their Hilbert code.
129  *
130  * This variant may use a maximum depth of 32 levels, and switches
131  * to lexicographical ordering if this is not enough.
132  *
133  * parameters:
134  * dim <-- 1D, 2D or 3D
135  * extents <-- coordinate extents for normalization (size: dim*2)
136  * n_coords <-- nomber of coordinates in array
137  * coords <-- coordinates in the grid (interlaced, not normalized)
138  * order --> pointer to pre-allocated ordering table
139  *----------------------------------------------------------------------------*/
140 
141 void
143  const cs_coord_t extents[],
144  cs_lnum_t n_coords,
145  const cs_coord_t coords[],
146  cs_lnum_t order[]);
147 
148 /*----------------------------------------------------------------------------
149  * Get the quantile associated to a Hilbert code using a binary search.
150  *
151  * No check is done to ensure that the code is present in the quantiles.
152  *
153  * parameters:
154  * n_quantiles <-- number of quantiles
155  * code <-- code we are searching for
156  * quantile_start <-- first Hilbert code in each quantile (size: n_quantiles)
157  *
158  * returns:
159  * id associated to the given code in the codes array.
160  *----------------------------------------------------------------------------*/
161 
162 size_t
163 fvm_hilbert_quantile_search(size_t n_quantiles,
164  fvm_hilbert_code_t code,
165  fvm_hilbert_code_t quantile_start[]);
166 
167 #if defined(HAVE_MPI)
168 
169 /*----------------------------------------------------------------------------
170  * Build a global Hilbert encoding rank index.
171  *
172  * The rank_index[i] contains the first Hilbert code assigned to rank [i].
173  *
174  * parameters:
175  * dim <-- 1D, 2D or 3D
176  * n_codes <-- number of Hilbert codes to be indexed
177  * hilbert_code <-- array of Hilbert codes to be indexed
178  * weight <-- weighting related to each code
179  * order <-- ordering array
180  * rank_index <-> pointer to the global Hilbert encoding rank index
181  * comm <-- MPI communicator on which we build the global index
182  *
183  * returns:
184  * the fit related to the Hilbert encoding distribution (lower is better).
185  *----------------------------------------------------------------------------*/
186 
187 double
188 fvm_hilbert_build_rank_index(int dim,
189  cs_lnum_t n_codes,
190  const fvm_hilbert_code_t hilbert_code[],
191  const cs_lnum_t weight[],
192  const cs_lnum_t order[],
193  fvm_hilbert_code_t rank_index[],
194  MPI_Comm comm);
195 
196 #endif /* HAVE_MPI */
197 
198 /*----------------------------------------------------------------------------*/
199 
200 #ifdef __cplusplus
201 }
202 #endif /* __cplusplus */
203 
204 #endif /* __FVM_HILBERT_H__ */
void fvm_hilbert_get_coord_extents(int dim, size_t n_coords, const cs_coord_t coords[], cs_coord_t g_extents[])
Definition: fvm_hilbert.c:1174
double fvm_hilbert_code_t
Definition: fvm_hilbert.h:56
double cs_coord_t
Definition: cs_defs.h:261
void fvm_hilbert_local_order_coords(int dim, const cs_coord_t extents[], cs_lnum_t n_coords, const cs_coord_t coords[], cs_lnum_t order[])
Definition: fvm_hilbert.c:1337
int cs_lnum_t
Definition: cs_defs.h:260
size_t fvm_hilbert_quantile_search(size_t n_quantiles, fvm_hilbert_code_t code, fvm_hilbert_code_t quantile_start[])
Definition: fvm_hilbert.c:1394
void fvm_hilbert_local_order(cs_lnum_t n_codes, const fvm_hilbert_code_t hilbert_codes[], cs_lnum_t order[])
Definition: fvm_hilbert.c:1292
void fvm_hilbert_encode_coords(int dim, const cs_coord_t extents[], cs_lnum_t n_coords, const cs_coord_t coords[], fvm_hilbert_code_t h_code[])
Definition: fvm_hilbert.c:1237