programmer's documentation
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-2015 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 #include "cs_defs.h"
31 
32 /*----------------------------------------------------------------------------
33  * Local headers
34  *----------------------------------------------------------------------------*/
35 
36 #include "fvm_defs.h"
37 
38 /*----------------------------------------------------------------------------*/
39 
41 
42 /*============================================================================
43  * Macro and type definitions
44  *============================================================================*/
45 
46 /* Hilbert code
47  (could be switched from double to long double for extened range) */
48 
49 typedef double fvm_hilbert_code_t;
50 
51 /*============================================================================
52  * Public function definitions
53  *============================================================================*/
54 
55 /*----------------------------------------------------------------------------
56  * Determine the global extents associated with a set of coordinates
57  *
58  * parameters:
59  * dim <-- spatial dimension
60  * n_coords <-- local number of coordinates
61  * coords <-- entity coordinates; size: n_entities*dim (interlaced)
62  * g_extents --> global extents (size: dim*2)
63  * comm <-- associated MPI communicator
64  *---------------------------------------------------------------------------*/
65 
66 #if defined(HAVE_MPI)
67 void
69  size_t n_coords,
70  const cs_coord_t coords[],
71  cs_coord_t g_extents[],
72  MPI_Comm comm);
73 #else
74 void
76  size_t n_coords,
77  const cs_coord_t coords[],
78  cs_coord_t g_extents[]);
79 #endif
80 
81 /*----------------------------------------------------------------------------
82  * Encode an array of coordinates.
83  *
84  * The caller is responsible for freeing the returned array once it is
85  * no longer useful.
86  *
87  * parameters:
88  * dim <-- 1D, 2D or 3D
89  * extents <-- coordinate extents for normalization (size: dim*2)
90  * n_coords <-- nomber of coordinates in array
91  * coords <-- coordinates in the grid (interlaced, not normalized)
92  * h_code --> array of corresponding Hilbert codes (size: n_coords)
93  *----------------------------------------------------------------------------*/
94 
95 void
97  const cs_coord_t extents[],
98  cs_lnum_t n_coords,
99  const cs_coord_t coords[],
100  fvm_hilbert_code_t h_code[]);
101 
102 /*----------------------------------------------------------------------------
103  * Locally order a list of Hilbert ids.
104  *
105  * This variant uses an encoding into floating-point numbers. In 3D, this
106  * limits us to 19 levels for a double, though using a long double could
107  * increase this range.
108  *
109  * parameters:
110  * n_codes <-- number of Hilbert ids to order
111  * hilbert_codes <-- array of Hilbert ids to order
112  * order --> pointer to pre-allocated ordering table
113  *----------------------------------------------------------------------------*/
114 
115 void
117  const fvm_hilbert_code_t hilbert_codes[],
118  cs_lnum_t order[]);
119 
120 /*----------------------------------------------------------------------------
121  * Locally order a list of coordinates based on their Hilbert code.
122  *
123  * This variant may use a maximum depth of 32 levels, and switches
124  * to lexicographical ordering if this is not enough.
125  *
126  * parameters:
127  * dim <-- 1D, 2D or 3D
128  * extents <-- coordinate extents for normalization (size: dim*2)
129  * n_coords <-- nomber of coordinates in array
130  * coords <-- coordinates in the grid (interlaced, not normalized)
131  * order --> pointer to pre-allocated ordering table
132  *----------------------------------------------------------------------------*/
133 
134 void
136  const cs_coord_t extents[],
137  cs_lnum_t n_coords,
138  const cs_coord_t coords[],
139  cs_lnum_t order[]);
140 
141 /*----------------------------------------------------------------------------
142  * Get the quantile associated to a Hilbert code using a binary search.
143  *
144  * No check is done to ensure that the code is present in the quantiles.
145  *
146  * parameters:
147  * n_quantiles <-- number of quantiles
148  * code <-- code we are searching for
149  * quantile_start <-- first Hilbert code in each quantile (size: n_quantiles)
150  *
151  * returns:
152  * id associated to the given code in the codes array.
153  *----------------------------------------------------------------------------*/
154 
155 size_t
156 fvm_hilbert_quantile_search(size_t n_quantiles,
157  fvm_hilbert_code_t code,
158  fvm_hilbert_code_t quantile_start[]);
159 
160 #if defined(HAVE_MPI)
161 
162 /*----------------------------------------------------------------------------
163  * Build a global Hilbert encoding rank index.
164  *
165  * The rank_index[i] contains the first Hilbert code assigned to rank [i].
166  *
167  * parameters:
168  * dim <-- 1D, 2D or 3D
169  * n_codes <-- number of Hilbert codes to be indexed
170  * hilbert_code <-- array of Hilbert codes to be indexed
171  * weight <-- weighting related to each code
172  * order <-- ordering array
173  * rank_index <-> pointer to the global Hilbert encoding rank index
174  * comm <-- MPI communicator on which we build the global index
175  *
176  * returns:
177  * the fit related to the Hilbert encoding distribution (lower is better).
178  *----------------------------------------------------------------------------*/
179 
180 double
181 fvm_hilbert_build_rank_index(int dim,
182  cs_lnum_t n_codes,
183  const fvm_hilbert_code_t hilbert_code[],
184  const cs_lnum_t weight[],
185  const cs_lnum_t order[],
186  fvm_hilbert_code_t rank_index[],
187  MPI_Comm comm);
188 
189 #endif /* HAVE_MPI */
190 
191 /*----------------------------------------------------------------------------*/
192 
194 
195 #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:1101
double fvm_hilbert_code_t
Definition: fvm_hilbert.h:49
#define BEGIN_C_DECLS
Definition: cs_defs.h:429
double cs_coord_t
Definition: cs_defs.h:293
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:1264
int cs_lnum_t
local mesh entity id
Definition: cs_defs.h:292
#define END_C_DECLS
Definition: cs_defs.h:430
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:1321
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:1219
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:1164