Line data Source code
1 : /**
2 : * @file linear_solver_internal.h
3 : * @brief Internal declarations for linear solver implementations
4 : *
5 : * This header is not part of the public API.
6 : */
7 :
8 : #ifndef CFD_LINEAR_SOLVER_INTERNAL_H
9 : #define CFD_LINEAR_SOLVER_INTERNAL_H
10 :
11 : #include "cfd/solvers/poisson_solver.h"
12 : #include <float.h>
13 : #include <math.h>
14 : #include <stdbool.h>
15 : #include <stdint.h>
16 : #include <limits.h>
17 :
18 : #ifndef M_PI
19 : #define M_PI 3.14159265358979323846
20 : #endif
21 :
22 : #ifdef __cplusplus
23 : extern "C" {
24 : #endif
25 :
26 : /* ============================================================================
27 : * FACTORY FUNCTIONS
28 : *
29 : * All SIMD backends use runtime CPU detection (AVX2/NEON) via the SIMD
30 : * dispatcher. See simd/linear_solver_simd_dispatch.c for details.
31 : * ============================================================================ */
32 :
33 : /* Jacobi solvers */
34 : poisson_solver_t* create_jacobi_scalar_solver(void);
35 : poisson_solver_t* create_jacobi_simd_solver(void);
36 :
37 : /* SOR solvers */
38 : poisson_solver_t* create_sor_scalar_solver(void);
39 : poisson_solver_t* create_sor_simd_solver(void);
40 :
41 : /* Red-Black SOR solvers */
42 : poisson_solver_t* create_redblack_scalar_solver(void);
43 : poisson_solver_t* create_redblack_simd_solver(void);
44 :
45 : #ifdef CFD_ENABLE_OPENMP
46 : poisson_solver_t* create_jacobi_omp_solver(void);
47 : poisson_solver_t* create_redblack_omp_solver(void);
48 : poisson_solver_t* create_cg_omp_solver(void);
49 : poisson_solver_t* create_bicgstab_omp_solver(void);
50 : #endif
51 :
52 : /* Conjugate Gradient solvers */
53 : poisson_solver_t* create_cg_scalar_solver(void);
54 : poisson_solver_t* create_cg_simd_solver(void);
55 :
56 : #ifdef CFD_HAS_CUDA
57 : /* GPU (CUDA) solvers — defined in linear/gpu/*.cu, linked via cfd_cuda */
58 : poisson_solver_t* create_jacobi_gpu_solver(void);
59 : poisson_solver_t* create_cg_gpu_solver(void);
60 : poisson_solver_t* create_bicgstab_gpu_solver(void);
61 : poisson_solver_t* create_redblack_gpu_solver(void);
62 : poisson_solver_t* create_sor_gpu_solver(void);
63 : #endif
64 :
65 : /* BiCGSTAB solvers (for non-symmetric systems) */
66 : poisson_solver_t* create_bicgstab_scalar_solver(void);
67 : poisson_solver_t* create_bicgstab_simd_solver(void);
68 :
69 : /* GMRES solvers (restarted GMRES(m) for non-symmetric systems) */
70 : poisson_solver_t* create_gmres_scalar_solver(void);
71 : poisson_solver_t* create_gmres_simd_solver(void);
72 :
73 : #ifdef CFD_ENABLE_OPENMP
74 : poisson_solver_t* create_gmres_omp_solver(void);
75 : #endif
76 :
77 : /* Geometric multigrid solvers (V/W/F cycles; scalar and OpenMP backends) */
78 : poisson_solver_t* create_multigrid_scalar_solver(void);
79 :
80 : #ifdef CFD_ENABLE_OPENMP
81 : poisson_solver_t* create_multigrid_omp_solver(void);
82 : #endif
83 :
84 : /**
85 : * Whether a (method, backend) pair implements params.helmholtz_shift.
86 : *
87 : * Default-deny. Currently: CG on the scalar and OpenMP backends, and not with
88 : * the multigrid preconditioner, whose inner V-cycle is built from default params and would
89 : * precondition with the unshifted operator. POISSON_PRECOND_JACOBI is fine --
90 : * it is one diagonal term.
91 : *
92 : * poisson_solver_check_config is what calls this; a backend that has not been
93 : * taught the shift fails loudly at init rather than silently solving the
94 : * unshifted equation, which is a wrong answer rather than a slow one.
95 : */
96 66 : static inline int poisson_solver_shift_supported(
97 : poisson_solver_method_t method,
98 : poisson_solver_backend_t backend,
99 : const poisson_solver_params_t* params) {
100 66 : if (method != POISSON_METHOD_CG
101 54 : || (backend != POISSON_BACKEND_SCALAR && backend != POISSON_BACKEND_OMP)) {
102 : return 0;
103 : }
104 54 : if (params && params->krylov.preconditioner == POISSON_PRECOND_MULTIGRID) {
105 : return 0;
106 : }
107 : return 1;
108 : }
109 :
110 : /**
111 : * Validate the whole configuration against the resolved method and backend.
112 : *
113 : * Called once from poisson_solver_init, and the only place that decides what a
114 : * given solver can honour. A parameter it cannot is refused here rather than
115 : * ignored: CFD_ERROR_UNSUPPORTED where the solver would have to implement
116 : * something it does not, CFD_ERROR_INVALID where the caller has asked for two
117 : * contradictory things or for something that could not take effect.
118 : *
119 : * Central rather than per-init because the alternative -- a check inside each of
120 : * the twenty-odd solver inits -- is what let BiCGSTAB ignore
121 : * params.krylov.preconditioner on every backend, three GPU solvers ignore a
122 : * caller's apply_bc, and would have let any of ~20 inits ignore a Helmholtz
123 : * shift, for as long as they have existed.
124 : */
125 : cfd_status_t poisson_solver_check_config(const poisson_solver_t* solver);
126 :
127 : /**
128 : * Boundary values for a Krylov iterate, before a residual is formed from it.
129 : *
130 : * The Krylov solvers (CG, BiCGSTAB, GMRES) update interior points only, so the
131 : * operator they invert is whatever their vectors' halos say it is. Residual and
132 : * operator have to agree, or the solve converges to a field solving neither
133 : * system: it returns an x with A_op*x = b + (A_op - A_residual)*x0, wrong by
134 : * O(x0/h^2) at every wall-adjacent point.
135 : *
136 : * The iterate carries the full boundary condition -- the interior-dependent part
137 : * and the lift. Search directions carry only the homogeneous part; see
138 : * poisson_solver_krylov_apply_bc_homogeneous(). Call this before the initial
139 : * residual and before any residual recomputed mid-solve (GMRES at each restart,
140 : * where the iterate has moved and the extension is stale). The final
141 : * poisson_solver_apply_bc() that fills the output halo stays as it is.
142 : */
143 : void poisson_solver_krylov_apply_bc(poisson_solver_t* solver, double* x);
144 :
145 : /**
146 : * Boundary values for a Krylov search direction, before every operator apply.
147 : *
148 : * Only the homogeneous part of the boundary condition: the zero-gradient
149 : * extension for the default walls, a zero halo for a custom (Dirichlet) hook,
150 : * whose prescribed values belong to the iterate and not to a direction. Applying
151 : * an inhomogeneous condition here would make the operator affine rather than
152 : * linear, which the Krylov recurrences do not describe.
153 : *
154 : * Required before each apply: the directions are rebuilt from interior-only
155 : * updates, so their halos are stale from the previous iteration otherwise.
156 : */
157 : void poisson_solver_krylov_apply_bc_homogeneous(poisson_solver_t* solver, double* v);
158 :
159 : /**
160 : * Whether the Krylov operator has a nullspace.
161 : *
162 : * True when every face is zero-gradient and no apply_bc hook is installed: the
163 : * discrete zero-gradient Laplacian is symmetric positive SEMI-definite, with the
164 : * constants in its nullspace. The system is then solvable only for a right-hand
165 : * side of zero interior mean, which poisson_solver_solve() checks and refuses
166 : * otherwise -- the solvers do NOT quietly project the rhs onto the compatible
167 : * subspace, because that solves a different problem than the caller asked for.
168 : * poisson_make_rhs_compatible() is the caller's way to comply.
169 : *
170 : * A prescribed face, or a hook, pins the level and makes the operator
171 : * nonsingular, where any rhs is admissible and mean-subtracting would be wrong.
172 : */
173 : int poisson_solver_krylov_is_singular(const poisson_solver_t* solver);
174 :
175 : /**
176 : * Create and initialize the inner solver of POISSON_PRECOND_MULTIGRID: one
177 : * multigrid V-cycle per preconditioner apply. Every CG backend that supports
178 : * the preconditioner builds it here, so all of them apply the same M.
179 : *
180 : * Dirichlet mode matches CG's interior operator (Krylov vectors carry a
181 : * permanent zero halo) and keeps M nonsingular; Jacobi smoothing with equal
182 : * pre/post sweeps keeps M symmetric, as CG requires.
183 : *
184 : * @param factory Multigrid backend factory (create_multigrid_<backend>_solver)
185 : * @param out Receives the initialized solver; written only on success
186 : * @return CFD_SUCCESS, CFD_ERROR_NOMEM, or the multigrid init status
187 : * (CFD_ERROR_INVALID for grid dims that are not 2^k+1)
188 : */
189 43 : static inline cfd_status_t poisson_solver_create_mg_precond(
190 : poisson_solver_t* (*factory)(void),
191 : size_t nx, size_t ny, size_t nz,
192 : double dx, double dy, double dz,
193 : const poisson_multigrid_params_t* requested,
194 : poisson_solver_t** out) {
195 43 : poisson_solver_t* mg = factory();
196 43 : if (!mg) {
197 : return CFD_ERROR_NOMEM;
198 : }
199 :
200 43 : poisson_solver_params_t mg_params = poisson_solver_params_default();
201 43 : if (requested) {
202 43 : mg_params.multigrid = *requested;
203 : }
204 :
205 : /* Four fields are the preconditioner's, not the caller's. A V-cycle with
206 : * weighted-Jacobi smoothing, Dirichlet coarse corrections and an equal
207 : * pre/post sweep count applies a symmetric operator; without that, M is not
208 : * symmetric and CG is no longer minimising over a Krylov space. W and F
209 : * cycles are not V applied harder -- whether they stay symmetric depends on
210 : * how the recursion composes, which is not something to assume here.
211 : *
212 : * poisson_solver_check_config resolves the sweep count by refusing an
213 : * unequal pair outright, and refuses a caller who names the other three, so
214 : * the assignments below overwrite nothing that was asked for: they fill in
215 : * fields the caller was required to leave at zero. The rest of the group --
216 : * pre_smooth/post_smooth, coarse_max_iter, max_levels -- is the caller's and
217 : * is forwarded above, which is what makes those tunable for PCG-MG at all.
218 : */
219 43 : mg_params.multigrid.cycle = MG_CYCLE_V;
220 43 : mg_params.multigrid.smoother = MG_SMOOTHER_JACOBI;
221 43 : mg_params.multigrid.bc = MG_BC_DIRICHLET;
222 :
223 43 : cfd_status_t status = poisson_solver_init(mg, nx, ny, nz, dx, dy, dz, &mg_params);
224 43 : if (status != CFD_SUCCESS) {
225 4 : poisson_solver_destroy(mg);
226 4 : return status;
227 : }
228 :
229 39 : *out = mg;
230 39 : return CFD_SUCCESS;
231 : }
232 :
233 : /* ============================================================================
234 : * CG ALGORITHM CONSTANTS
235 : * ============================================================================ */
236 :
237 : /**
238 : * Threshold for detecting CG breakdown (division by near-zero).
239 : * If (p, Ap) or (r, r) falls below this, the algorithm has stagnated
240 : * or encountered a singular/near-singular system.
241 : */
242 : #define CG_BREAKDOWN_THRESHOLD 1e-30
243 :
244 : /**
245 : * Macro for CG breakdown check with early return.
246 : * Used when a denominator (p_dot_Ap or r_dot_r) becomes too small.
247 : *
248 : * @param value The value to check against breakdown threshold
249 : * @param stats Pointer to stats structure (may be NULL)
250 : * @param iter Current iteration index
251 : * @param res_norm Current residual norm
252 : * @param start_time Start time for elapsed time calculation
253 : */
254 : #define CG_CHECK_BREAKDOWN(value, stats, iter, res_norm, start_time) \
255 : do { \
256 : if (fabs(value) < CG_BREAKDOWN_THRESHOLD) { \
257 : if (stats) { \
258 : (stats)->status = POISSON_STAGNATED; \
259 : (stats)->iterations = (iter) + 1; \
260 : (stats)->final_residual = (res_norm); \
261 : (stats)->elapsed_time_ms = poisson_solver_get_time_ms() - (start_time); \
262 : } \
263 : return CFD_ERROR_MAX_ITER; \
264 : } \
265 : } while (0)
266 :
267 : /* ============================================================================
268 : * BICGSTAB ALGORITHM CONSTANTS
269 : * ============================================================================ */
270 :
271 : /**
272 : * Threshold for detecting BiCGSTAB breakdown (division by near-zero).
273 : * If rho, (r_hat,v), or (t,t) falls below this, the algorithm has stagnated.
274 : */
275 : #define BICGSTAB_BREAKDOWN_THRESHOLD 1e-30
276 :
277 : /* ============================================================================
278 : * GMRES ALGORITHM CONSTANTS
279 : * ============================================================================ */
280 :
281 : /**
282 : * Default restart length m for GMRES(m) when params.krylov.restart <= 0.
283 : * The Krylov basis holds m+1 grid-sized vectors, so this bounds memory.
284 : */
285 : #define GMRES_DEFAULT_RESTART 30
286 :
287 : /**
288 : * Threshold for detecting GMRES happy (lucky) breakdown.
289 : * When the Arnoldi subdiagonal H[j+1,j] (a vector norm) falls below this, the
290 : * exact solution already lies in the current Krylov subspace: this signals
291 : * CONVERGENCE, not failure. Larger than CG_BREAKDOWN_THRESHOLD because
292 : * H[j+1,j] is an sqrt-scaled norm rather than a squared dot product.
293 : */
294 : #define GMRES_BREAKDOWN_THRESHOLD 1e-12
295 :
296 : /* ============================================================================
297 : * OPENMP LOOP BOUNDS
298 : * ============================================================================ */
299 :
300 : /**
301 : * Convert size_t to int for OpenMP loop bounds.
302 : * OpenMP (MSVC 2.0) requires int loop variables, but grid dimensions are size_t.
303 : * Shared by the OMP primitives and the SIMD solver templates.
304 : *
305 : * @param val The size_t value to convert
306 : * @return int value, or 0 on overflow (CFD_ERROR_LIMIT_EXCEEDED set)
307 : */
308 1193073 : static inline int poisson_solver_size_to_int(size_t val) {
309 1193073 : if (val > (size_t)INT_MAX) {
310 0 : cfd_set_error(CFD_ERROR_LIMIT_EXCEEDED, "Grid size exceeds INT_MAX for OpenMP loop");
311 0 : return 0;
312 : }
313 1193073 : return (int)val;
314 : }
315 :
316 : /* ============================================================================
317 : * GRID SIZE LIMITS
318 : * ============================================================================ */
319 :
320 : /**
321 : * Validate grid dimensions at init and compute the field size n = nx*ny*nz.
322 : *
323 : * Rejects nx or ny above INT_MAX, where poisson_solver_size_to_int returns 0 and
324 : * every int-bounded primitive loop becomes a no-op (a zero residual would then
325 : * read as convergence), and grids where `vectors` grid-sized double arrays would
326 : * not fit in size_t bytes. Each multiplication is checked before it is taken, so
327 : * n cannot wrap and work arrays cannot be allocated undersized.
328 : * Assumes nx, ny >= 3 (validated by poisson_solver_init).
329 : *
330 : * @param vectors number of grid-sized double arrays in the largest single
331 : * allocation (>= 1)
332 : * @param n_out receives nx*ny*nz on success
333 : * @return CFD_SUCCESS, or CFD_ERROR_LIMIT_EXCEEDED (error set)
334 : */
335 546 : static inline cfd_status_t poisson_solver_validate_grid_size(
336 : size_t nx, size_t ny, size_t nz, size_t vectors, size_t* n_out)
337 : {
338 546 : size_t max_n = SIZE_MAX / sizeof(double) / vectors;
339 546 : if (nx > (size_t)INT_MAX || ny > (size_t)INT_MAX ||
340 532 : ny > max_n / nx || nz > max_n / (nx * ny)) {
341 21 : cfd_set_error(CFD_ERROR_LIMIT_EXCEEDED, "Grid size exceeds indexable limits");
342 21 : return CFD_ERROR_LIMIT_EXCEEDED;
343 : }
344 525 : *n_out = nx * ny * nz;
345 525 : return CFD_SUCCESS;
346 : }
347 :
348 : /* ============================================================================
349 : * SIMD BACKEND AVAILABILITY (Runtime detection)
350 : * ============================================================================ */
351 :
352 : /**
353 : * Check if SIMD backend is available at runtime.
354 : * Uses cfd_detect_simd_arch() from cpu_features.h.
355 : */
356 : bool poisson_solver_simd_backend_available(void);
357 :
358 : /**
359 : * Get the name of the detected SIMD architecture.
360 : * Returns "avx2", "neon", or "none".
361 : */
362 : const char* poisson_solver_simd_get_arch_name(void);
363 :
364 : /* ============================================================================
365 : * 3D LOOP BOUNDS HELPERS
366 : *
367 : * Centralizes the nz-dependent logic so each solver's init doesn't repeat it.
368 : * When nz==1 (2D): stride_z=0, k_start=0, k_end=1 → single k-iteration,
369 : * z-stencil terms vanish naturally.
370 : * ============================================================================ */
371 :
372 : /**
373 : * Compute 3D loop bounds from solver dimensions.
374 : */
375 195465 : static inline void poisson_solver_compute_3d_bounds(
376 : size_t nz, size_t nx, size_t ny,
377 : size_t* stride_z, size_t* k_start, size_t* k_end)
378 : {
379 195465 : *stride_z = (nz > 1) ? (nx * ny) : 0;
380 195465 : *k_start = (nz > 1) ? 1 : 0;
381 195465 : *k_end = (nz > 1) ? (nz - 1) : 1;
382 : }
383 :
384 : /**
385 : * Compute inv_dz2 safely (0.0 when dz==0, avoiding division by zero).
386 : */
387 355866 : static inline double poisson_solver_compute_inv_dz2(double dz) {
388 224829 : return (dz > 0.0) ? (1.0 / (dz * dz)) : 0.0;
389 : }
390 :
391 : /* ============================================================================
392 : * ROUND-OFF FLOOR OF THE RESIDUAL
393 : * ============================================================================ */
394 :
395 : /**
396 : * Margin of the stopping floor over the round-off it stands for. The measured
397 : * max-norm floor of a converged multigrid solve is 0.6-1.3 times
398 : * eps * |x|_inf * (2/dx^2 + 2/dy^2), from 129^2 to 1025^2; a residual ten times
399 : * that still pins x to a few eps * |x|.
400 : */
401 : #define POISSON_ROUNDOFF_FACTOR 10.0
402 :
403 : /** The norm a solver measures its residual in. */
404 : typedef enum {
405 : POISSON_NORM_MAX = 0, /**< max |r|: poisson_solver_compute_residual() */
406 : POISSON_NORM_L2 = 1 /**< sqrt(sum r^2) over the interior: the Krylov solvers */
407 : } poisson_norm_t;
408 :
409 : /**
410 : * Smallest residual that can be told apart from round-off at x.
411 : *
412 : * The stencil adds terms of size |x|/h^2 that cancel, so no evaluation of
413 : * lap(x) - rhs is more accurate than about eps * |x| * (2/dx^2 + 2/dy^2 +
414 : * 2/dz^2 + |sigma|). That floor grows as |x|/h^2 while absolute_tolerance is
415 : * fixed, so on a fine grid, or with a large pressure, a stopping target set by
416 : * absolute_tolerance can lie below anything the solver is able to measure: it
417 : * then iterates until max_iterations and reports CFD_ERROR_MAX_ITER on a field
418 : * that was already converged. Every stopping rule takes the larger of its
419 : * target and this floor.
420 : *
421 : * In the L2 norm the per-point errors add in quadrature over the interior,
422 : * hence the sqrt of its size.
423 : */
424 165104 : static inline double poisson_solver_residual_floor(const poisson_solver_t* solver,
425 : const double* x, poisson_norm_t norm)
426 : {
427 165104 : size_t nz = (solver->nz > 1) ? solver->nz : 1;
428 165104 : size_t total = solver->nx * solver->ny * nz;
429 165104 : double x_max = 0.0;
430 500477493 : for (size_t k = 0; k < total; k++) {
431 500312389 : double a = fabs(x[k]);
432 500312389 : if (a > x_max) {
433 3867663 : x_max = a;
434 : }
435 : }
436 330208 : double stencil = (2.0 / (solver->dx * solver->dx)) + (2.0 / (solver->dy * solver->dy)) +
437 165104 : (2.0 * poisson_solver_compute_inv_dz2(solver->dz)) +
438 165104 : fabs(solver->params.helmholtz_shift);
439 165104 : double floor_res = POISSON_ROUNDOFF_FACTOR * DBL_EPSILON * x_max * stencil;
440 165104 : if (norm == POISSON_NORM_L2) {
441 16690 : size_t interior = (solver->nx - 2) * (solver->ny - 2) * ((nz > 1) ? (nz - 2) : 1);
442 16690 : floor_res *= sqrt((double)interior);
443 : }
444 165104 : return floor_res;
445 : }
446 :
447 : /** The residual a solve must reach: max(tolerance * r0, absolute_tolerance, floor). */
448 17403 : static inline double poisson_solver_stop_target(const poisson_solver_params_t* params,
449 : double initial_res, double floor_res)
450 : {
451 17403 : double target = params->tolerance * initial_res;
452 17403 : if (target < params->absolute_tolerance) {
453 4566 : target = params->absolute_tolerance;
454 : }
455 17403 : return (target < floor_res) ? floor_res : target;
456 : }
457 :
458 : /** A start this close to the solution needs no iteration: max(absolute_tolerance, floor). */
459 163805 : static inline double poisson_solver_done_target(const poisson_solver_params_t* params,
460 : double floor_res)
461 : {
462 163805 : return (params->absolute_tolerance < floor_res) ? floor_res : params->absolute_tolerance;
463 : }
464 :
465 : /* ============================================================================
466 : * OPTIMAL SOR OMEGA COMPUTATION
467 : * ============================================================================ */
468 :
469 : /**
470 : * Compute optimal SOR relaxation parameter for a 2D/3D Laplacian.
471 : *
472 : * Uses the Jacobi spectral radius for a rectangular grid:
473 : * 2D: rho_J = [cos(pi/(nx-1))/dx^2 + cos(pi/(ny-1))/dy^2]
474 : * / [1/dx^2 + 1/dy^2]
475 : * 3D: rho_J = [cos(pi/(nx-1))/dx^2 + cos(pi/(ny-1))/dy^2
476 : * + cos(pi/(nz-1))/dz^2]
477 : * / [1/dx^2 + 1/dy^2 + 1/dz^2]
478 : * omega_opt = 2 / (1 + sqrt(1 - rho_J^2))
479 : *
480 : * When nz <= 1 or dz <= 0, the z-component is ignored and the 2D formula
481 : * is used.
482 : */
483 5 : static inline double poisson_solver_compute_optimal_omega(
484 : size_t nx, size_t ny, size_t nz,
485 : double dx, double dy, double dz)
486 : {
487 5 : double inv_dx2 = 1.0 / (dx * dx);
488 5 : double inv_dy2 = 1.0 / (dy * dy);
489 5 : double inv_dz2 = poisson_solver_compute_inv_dz2(dz);
490 :
491 5 : double num = cos(M_PI / (double)(nx - 1)) * inv_dx2
492 5 : + cos(M_PI / (double)(ny - 1)) * inv_dy2;
493 5 : double denom = inv_dx2 + inv_dy2;
494 :
495 5 : if (nz > 1 && inv_dz2 > 0.0) {
496 0 : num += cos(M_PI / (double)(nz - 1)) * inv_dz2;
497 0 : denom += inv_dz2;
498 : }
499 :
500 5 : double rho_j = num / denom;
501 5 : return 2.0 / (1.0 + sqrt(1.0 - (rho_j * rho_j)));
502 : }
503 :
504 : /**
505 : * Optimal SOR omega for zero-gradient (Neumann) walls.
506 : *
507 : * Relaxed as poisson_solver_wall_omega() describes, the iteration is SOR on the
508 : * Neumann matrix A itself, which is consistently ordered, so Young's
509 : * omega_opt = 2 / (1 + sqrt(1 - rho_J^2)) applies. rho_J = 1 - lambda, with lambda
510 : * the smallest nonzero eigenvalue of A v = lambda D v, D the diagonal of A; the
511 : * zero eigenvalue is the constant, the null space every Neumann problem has.
512 : *
513 : * The slowest mode varies as cos((i - 1/2) pi / N_a) along one axis a, where N_a
514 : * is its number of interior points, and is constant along the others. Its
515 : * Rayleigh quotient is
516 : * lambda_a = w_a (2 - 2 cos(pi / N_a)) / (factor - deficit_a)
517 : * deficit_a = w_a (4 / N_a) cos^2(pi / (2 N_a)) + sum over b != a of w_b (2 / N_b)
518 : * with w_b = 1/h_b^2, factor = 2 (w_x + w_y + w_z) the diagonal away from the
519 : * walls, and deficit_a what the walls take off the diagonal as that mode weighs
520 : * it. lambda is the smallest lambda_a. A Rayleigh quotient can only overestimate
521 : * the eigenvalue, so the omega this gives never exceeds the optimum, and it
522 : * approaches it as the grid grows.
523 : *
524 : * An axis with fewer than two interior points has no such mode and is skipped.
525 : * A grid with at most two interior points in all has no slow mode, and omega is
526 : * 1: a lone point has nothing to relax against, and two points have only the
527 : * alternating mode besides the constant. Its lambda is 2, so rho_J = -1 would
528 : * put omega at 2, yet SOR damps it by (1 - omega)^2 per sweep and omega = 1
529 : * removes it in one.
530 : */
531 43 : static inline double poisson_solver_compute_neumann_omega(
532 : size_t nx, size_t ny, size_t nz,
533 : double dx, double dy, double dz)
534 : {
535 43 : size_t n[3] = { nx, ny, nz };
536 43 : double w[3] = { 1.0 / (dx * dx), 1.0 / (dy * dy), 0.0 };
537 43 : if (nz > 1) {
538 10 : w[2] = poisson_solver_compute_inv_dz2(dz);
539 : }
540 43 : double factor = 2.0 * (w[0] + w[1] + w[2]);
541 :
542 : /* Interior points per active axis; a 2D grid has none along z */
543 43 : double interior[3];
544 43 : double points = 1.0;
545 172 : for (int a = 0; a < 3; a++) {
546 129 : interior[a] = (w[a] > 0.0) ? (double)(n[a] - 2) : 0.0;
547 129 : if (interior[a] > 0.0) {
548 91 : points *= interior[a];
549 : }
550 : }
551 43 : if (points <= 2.0) {
552 : return 1.0;
553 : }
554 :
555 : double lambda = -1.0;
556 160 : for (int a = 0; a < 3; a++) {
557 120 : if (interior[a] < 2.0) {
558 36 : continue;
559 : }
560 84 : double half = cos(M_PI / (2.0 * interior[a]));
561 84 : double deficit = w[a] * (4.0 / interior[a]) * half * half;
562 336 : for (int b = 0; b < 3; b++) {
563 252 : if (b != a && interior[b] >= 1.0) {
564 96 : deficit += w[b] * (2.0 / interior[b]);
565 : }
566 : }
567 84 : double mode = w[a] * (2.0 - 2.0 * cos(M_PI / interior[a])) / (factor - deficit);
568 84 : if (lambda < 0.0 || mode < lambda) {
569 120 : lambda = mode;
570 : }
571 : }
572 40 : double rho_j = 1.0 - lambda;
573 40 : return 2.0 / (1.0 + sqrt(1.0 - (rho_j * rho_j)));
574 : }
575 :
576 : /* ============================================================================
577 : * SOR RELAXATION AT ZERO-GRADIENT WALLS
578 : * ============================================================================ */
579 :
580 : /**
581 : * Stencil weight of the zero-gradient walls a point touches along one axis:
582 : * inv_h2 for each of its two neighbours on that axis that is a wall. With n
583 : * points along the axis, walls included, interior index 1 touches the low wall
584 : * and n - 2 the high one; a lone interior point (n == 3) touches both.
585 : */
586 36263926 : static inline double poisson_solver_wall_weight(size_t index, size_t n, double inv_h2)
587 : {
588 36263926 : int walls = (index == 1) + (index + 2 == n);
589 36263926 : return walls * inv_h2;
590 : }
591 :
592 : /**
593 : * Relaxation factor for a point beside the default zero-gradient walls.
594 : *
595 : * poisson_solver_apply_bc() copies each wall from its inner neighbour after the
596 : * sweep, so while sweeping, a point next to a wall reads its own previous value
597 : * through the copy. Relaxed with the plain omega, that stale self-coupling leaves
598 : * the iteration inconsistently ordered: SOR theory no longer predicts its best
599 : * omega, which lies well above any formula.
600 : *
601 : * Scaling the point's step by factor / (factor - wall_weight) removes the stale
602 : * term. The update becomes relaxation against the point's real neighbours only,
603 : * which is SOR on the Neumann matrix itself, whose optimum
604 : * poisson_solver_compute_neumann_omega() gives. factor is the full stencil weight
605 : * 2 (1/dx^2 + 1/dy^2 + 1/dz^2) and wall_weight the sum of
606 : * poisson_solver_wall_weight() over the axes: on a square 2D grid an edge point
607 : * relaxes with 4/3 omega and a corner point with 2 omega. The converged solution
608 : * is unchanged, because with the walls copied both updates solve the same
609 : * equation.
610 : *
611 : * A point whose every neighbour is a wall has nothing to relax against and keeps
612 : * its value.
613 : */
614 36263926 : static inline double poisson_solver_wall_omega(double omega, double factor, double wall_weight)
615 : {
616 36263926 : if (wall_weight <= 0.0) {
617 : return omega;
618 : }
619 22031721 : double interior = factor - wall_weight;
620 22031721 : return (interior > 0.0) ? omega * factor / interior : 0.0;
621 : }
622 :
623 : /**
624 : * Whether a CPU solver relaxes against the default zero-gradient wall copy.
625 : * A caller-supplied apply_bc holds wall values that are data rather than copies
626 : * of the interior, so its points keep the plain omega.
627 : */
628 135545 : static inline int poisson_solver_uses_default_walls(const poisson_solver_t* solver)
629 : {
630 135497 : return solver->apply_bc == NULL;
631 : }
632 :
633 : /**
634 : * Relaxation factors for one row of interior points (fixed j and k): w_row for
635 : * the points away from the x-walls, w_edge for the first and last (i == 1 and
636 : * i == nx - 2). Both are the plain omega when walls is 0.
637 : */
638 20404895 : static inline void poisson_solver_row_omegas(
639 : int walls, double omega, double factor,
640 : size_t nx, size_t ny, size_t nz, size_t j, size_t k,
641 : double inv_dx2, double inv_dy2, double inv_dz2,
642 : double* w_row, double* w_edge)
643 : {
644 20404895 : if (!walls) {
645 2272932 : *w_row = omega;
646 2272932 : *w_edge = omega;
647 2272932 : return;
648 : }
649 18131963 : double w_yz = poisson_solver_wall_weight(j, ny, inv_dy2)
650 18131963 : + poisson_solver_wall_weight(k, nz, inv_dz2);
651 18131963 : *w_row = poisson_solver_wall_omega(omega, factor, w_yz);
652 18131963 : *w_edge = poisson_solver_wall_omega(omega, factor,
653 18131963 : w_yz + poisson_solver_wall_weight(1, nx, inv_dx2));
654 : }
655 :
656 : /**
657 : * The omega a SOR or Red-Black SOR solver relaxes with.
658 : *
659 : * Gauss-Seidel is SOR at omega = 1, whatever params.sor.omega says. Otherwise an
660 : * explicit omega > 0 is used as given, and omega <= 0, the default, asks for the
661 : * optimum: the Neumann formula for the default wall copy, and the Dirichlet
662 : * formula above when the caller supplies its own apply_bc. poisson_solver_init()
663 : * fills in the grid before calling the backend init that resolves omega, so a
664 : * custom apply_bc must be installed before it.
665 : */
666 731 : static inline double poisson_solver_resolve_omega(const poisson_solver_t* solver, double omega)
667 : {
668 731 : if (solver->method == POISSON_METHOD_GAUSS_SEIDEL) {
669 : return 1.0;
670 : }
671 727 : if (omega > 0.0) {
672 : return omega;
673 : }
674 48 : if (poisson_solver_uses_default_walls(solver)) {
675 43 : return poisson_solver_compute_neumann_omega(
676 43 : solver->nx, solver->ny, solver->nz, solver->dx, solver->dy, solver->dz);
677 : }
678 5 : return poisson_solver_compute_optimal_omega(
679 5 : solver->nx, solver->ny, solver->nz, solver->dx, solver->dy, solver->dz);
680 : }
681 :
682 : /* ============================================================================
683 : * INTERNAL HELPER FUNCTIONS
684 : * ============================================================================ */
685 :
686 : /**
687 : * Common solve loop used by all iterative solvers
688 : *
689 : * Implements the iteration control, convergence checking, and statistics.
690 : *
691 : * @param solver Initialized solver
692 : * @param x Solution vector
693 : * @param x_temp Temporary buffer
694 : * @param rhs Right-hand side
695 : * @param stats Output statistics
696 : * @return CFD_SUCCESS if converged
697 : */
698 : cfd_status_t poisson_solver_solve_common(
699 : poisson_solver_t* solver,
700 : double* x,
701 : double* x_temp,
702 : const double* rhs,
703 : poisson_solver_stats_t* stats);
704 :
705 : /**
706 : * Get current time in milliseconds (platform-independent)
707 : */
708 : double poisson_solver_get_time_ms(void);
709 :
710 : #ifdef __cplusplus
711 : }
712 : #endif
713 :
714 : #endif /* CFD_LINEAR_SOLVER_INTERNAL_H */
|