Line data Source code
1 : /**
2 : * @file linear_solver_bicgstab.c
3 : * @brief BiCGSTAB solver - scalar CPU implementation
4 : *
5 : * Biconjugate Gradient Stabilized (BiCGSTAB) method for solving Ax = b where A
6 : * may be non-symmetric. This is useful for advection-dominated problems where
7 : * the discretized operator is not symmetric.
8 : *
9 : * BiCGSTAB characteristics:
10 : * - Works for non-symmetric matrices (unlike CG which requires SPD)
11 : * - Smoother convergence than BiCG (avoids irregular convergence behavior)
12 : * - Requires 2 matrix-vector products per iteration
13 : * - Requires 4 inner products and 4 axpy operations per iteration
14 : * - Needs storage for 6 vectors: r, r_hat, p, v, s, t
15 : *
16 : * Algorithm (van der Vorst, 1992):
17 : * r_0 = b - A*x_0
18 : * r_hat = r_0 (arbitrary, typically r_0)
19 : * rho_0 = alpha = omega = 1
20 : * v_0 = p_0 = 0
21 : *
22 : * for k = 1, 2, 3, ...
23 : * rho_k = (r_hat, r_{k-1})
24 : * beta = (rho_k / rho_{k-1}) * (alpha / omega)
25 : * p_k = r_{k-1} + beta * (p_{k-1} - omega * v_{k-1})
26 : * v_k = A * p_k
27 : * alpha = rho_k / (r_hat, v_k)
28 : * s = r_{k-1} - alpha * v_k
29 : * t = A * s
30 : * omega = (t, s) / (t, t)
31 : * x_k = x_{k-1} + alpha * p_k + omega * s
32 : * r_k = s - omega * t
33 : *
34 : * Note: For the Poisson equation with symmetric BCs, CG is preferred.
35 : * BiCGSTAB is provided for future use with non-symmetric operators.
36 : */
37 :
38 : #include "../linear_solver_internal.h"
39 :
40 : #include "cfd/core/indexing.h"
41 : #include "cfd/core/logging.h"
42 : #include "cfd/core/memory.h"
43 :
44 : #include <math.h>
45 : #include <string.h>
46 :
47 : /* ============================================================================
48 : * BICGSTAB CONTEXT
49 : * ============================================================================ */
50 :
51 : typedef struct {
52 : double dx2; /* dx^2 */
53 : double dy2; /* dy^2 */
54 : double inv_dz2; /* 1/dz^2 (0 for 2D) */
55 :
56 : size_t stride_z; /* nx*ny for 3D, 0 for 2D */
57 : size_t k_start; /* first interior k index */
58 : size_t k_end; /* one-past-last interior k index */
59 :
60 : /* BiCGSTAB working vectors (allocated during init) */
61 : double* r; /* Residual vector */
62 : double* r_hat; /* Shadow residual (typically r_0) */
63 : double* p; /* Search direction */
64 : double* v; /* A * p */
65 : double* s; /* Intermediate residual */
66 : double* t; /* A * s */
67 :
68 : int initialized;
69 : } bicgstab_context_t;
70 :
71 : /* ============================================================================
72 : * HELPER FUNCTIONS
73 : * ============================================================================ */
74 :
75 : /**
76 : * Compute dot product of two vectors (interior points only)
77 : */
78 585 : static double dot_product(const double* a, const double* b,
79 : size_t nx, size_t ny,
80 : size_t k_start, size_t k_end, size_t stride_z) {
81 585 : double sum = 0.0;
82 3062 : for (size_t k = k_start; k < k_end; k++) {
83 55344 : for (size_t j = 1; j < ny - 1; j++) {
84 1646800 : for (size_t i = 1; i < nx - 1; i++) {
85 1593341 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
86 1593341 : sum += a[idx] * b[idx];
87 : }
88 : }
89 : }
90 1484 : return sum;
91 : }
92 :
93 : /**
94 : * Compute y = y + alpha * x (interior points only)
95 : */
96 : static void axpy(double alpha, const double* x, double* y,
97 : size_t nx, size_t ny,
98 : size_t k_start, size_t k_end, size_t stride_z) {
99 42 : for (size_t k = k_start; k < k_end; k++) {
100 608 : for (size_t j = 1; j < ny - 1; j++) {
101 10656 : for (size_t i = 1; i < nx - 1; i++) {
102 10083 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
103 10083 : y[idx] += alpha * x[idx];
104 : }
105 : }
106 : }
107 : }
108 :
109 : /**
110 : * Apply negative Laplacian operator: Ap = -nabla^2(p)
111 : * For Poisson equation: nabla^2(x) = rhs, we solve -nabla^2(x) = -rhs
112 : * which is SPD with positive eigenvalues.
113 : */
114 585 : static void apply_laplacian(const double* p, double* Ap,
115 : size_t nx, size_t ny,
116 : double dx2, double dy2, double inv_dz2,
117 : size_t k_start, size_t k_end, size_t stride_z) {
118 585 : double dx2_inv = 1.0 / dx2;
119 585 : double dy2_inv = 1.0 / dy2;
120 :
121 1198 : for (size_t k = k_start; k < k_end; k++) {
122 18112 : for (size_t j = 1; j < ny - 1; j++) {
123 537408 : for (size_t i = 1; i < nx - 1; i++) {
124 519909 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
125 :
126 519909 : double laplacian =
127 519909 : (p[idx + 1] - 2.0 * p[idx] + p[idx - 1]) * dx2_inv
128 519909 : + (p[idx + nx] - 2.0 * p[idx] + p[idx - nx]) * dy2_inv
129 519909 : + (p[idx + stride_z] + p[idx - stride_z] - 2.0 * p[idx]) * inv_dz2;
130 519909 : Ap[idx] = -laplacian;
131 : }
132 : }
133 : }
134 585 : }
135 :
136 : /**
137 : * Compute initial residual: r = b - A*x
138 : * For our formulation: r = -rhs - (-nabla^2 x) = -rhs + nabla^2 x
139 : */
140 18 : static void compute_residual(const double* x, const double* rhs, double* r,
141 : size_t nx, size_t ny,
142 : double dx2, double dy2, double inv_dz2,
143 : size_t k_start, size_t k_end, size_t stride_z) {
144 18 : double dx2_inv = 1.0 / dx2;
145 18 : double dy2_inv = 1.0 / dy2;
146 :
147 64 : for (size_t k = k_start; k < k_end; k++) {
148 1008 : for (size_t j = 1; j < ny - 1; j++) {
149 34576 : for (size_t i = 1; i < nx - 1; i++) {
150 33614 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
151 :
152 : /* Laplacian(x) = d^2x/dx^2 + d^2x/dy^2 */
153 33614 : double laplacian =
154 33614 : (x[idx + 1] - 2.0 * x[idx] + x[idx - 1]) * dx2_inv
155 33614 : + (x[idx + nx] - 2.0 * x[idx] + x[idx - nx]) * dy2_inv
156 33614 : + (x[idx + stride_z] + x[idx - stride_z] - 2.0 * x[idx]) * inv_dz2;
157 :
158 : /* r = b - Ax = -rhs - (-laplacian) = -rhs + laplacian */
159 33614 : r[idx] = -rhs[idx] + laplacian;
160 : }
161 : }
162 : }
163 18 : }
164 :
165 : /**
166 : * Copy vector: dst = src (interior points only)
167 : */
168 18 : static void copy_vector(const double* src, double* dst,
169 : size_t nx, size_t ny,
170 : size_t k_start, size_t k_end, size_t stride_z) {
171 64 : for (size_t k = k_start; k < k_end; k++) {
172 1008 : for (size_t j = 1; j < ny - 1; j++) {
173 34576 : for (size_t i = 1; i < nx - 1; i++) {
174 33614 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
175 33614 : dst[idx] = src[idx];
176 : }
177 : }
178 : }
179 : }
180 :
181 : /**
182 : * Set vector to zero (interior points only)
183 : */
184 : static void zero_vector(double* v, size_t nx, size_t ny,
185 : size_t k_start, size_t k_end, size_t stride_z) {
186 92 : for (size_t k = k_start; k < k_end; k++) {
187 2016 : for (size_t j = 1; j < ny - 1; j++) {
188 69152 : for (size_t i = 1; i < nx - 1; i++) {
189 67228 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
190 67228 : v[idx] = 0.0;
191 : }
192 : }
193 : }
194 : }
195 :
196 : /* ============================================================================
197 : * BICGSTAB SCALAR IMPLEMENTATION
198 : * ============================================================================ */
199 :
200 21 : static cfd_status_t bicgstab_scalar_init(
201 : poisson_solver_t* solver,
202 : size_t nx, size_t ny, size_t nz,
203 : double dx, double dy, double dz,
204 : const poisson_solver_params_t* params)
205 : {
206 21 : (void)params;
207 :
208 21 : bicgstab_context_t* ctx = (bicgstab_context_t*)cfd_calloc(1, sizeof(bicgstab_context_t));
209 21 : if (!ctx) {
210 : return CFD_ERROR_NOMEM;
211 : }
212 :
213 21 : ctx->dx2 = dx * dx;
214 21 : ctx->dy2 = dy * dy;
215 21 : ctx->inv_dz2 = poisson_solver_compute_inv_dz2(dz);
216 21 : poisson_solver_compute_3d_bounds(nz, nx, ny, &ctx->stride_z, &ctx->k_start, &ctx->k_end);
217 :
218 : /* Allocate working vectors */
219 21 : size_t n = nx * ny * nz;
220 21 : ctx->r = (double*)cfd_calloc(n, sizeof(double));
221 21 : ctx->r_hat = (double*)cfd_calloc(n, sizeof(double));
222 21 : ctx->p = (double*)cfd_calloc(n, sizeof(double));
223 21 : ctx->v = (double*)cfd_calloc(n, sizeof(double));
224 21 : ctx->s = (double*)cfd_calloc(n, sizeof(double));
225 21 : ctx->t = (double*)cfd_calloc(n, sizeof(double));
226 :
227 21 : if (!ctx->r || !ctx->r_hat || !ctx->p || !ctx->v || !ctx->s || !ctx->t) {
228 0 : cfd_free(ctx->r);
229 0 : cfd_free(ctx->r_hat);
230 0 : cfd_free(ctx->p);
231 0 : cfd_free(ctx->v);
232 0 : cfd_free(ctx->s);
233 0 : cfd_free(ctx->t);
234 0 : cfd_free(ctx);
235 0 : return CFD_ERROR_NOMEM;
236 : }
237 :
238 21 : ctx->initialized = 1;
239 21 : solver->context = ctx;
240 21 : return CFD_SUCCESS;
241 : }
242 :
243 26 : static void bicgstab_scalar_destroy(poisson_solver_t* solver) {
244 26 : if (solver && solver->context) {
245 21 : bicgstab_context_t* ctx = (bicgstab_context_t*)solver->context;
246 21 : cfd_free(ctx->r);
247 21 : cfd_free(ctx->r_hat);
248 21 : cfd_free(ctx->p);
249 21 : cfd_free(ctx->v);
250 21 : cfd_free(ctx->s);
251 21 : cfd_free(ctx->t);
252 21 : cfd_free(ctx);
253 21 : solver->context = NULL;
254 : }
255 26 : }
256 :
257 : /**
258 : * BiCGSTAB solve function
259 : *
260 : * BiCGSTAB uses its own solve loop because:
261 : * 1. It maintains complex state across iterations (rho, omega, alpha)
262 : * 2. Has two convergence checks per iteration (after s and after r)
263 : * 3. Requires two matrix-vector products per iteration
264 : */
265 18 : static cfd_status_t bicgstab_scalar_solve(
266 : poisson_solver_t* solver,
267 : double* x,
268 : double* x_temp,
269 : const double* rhs,
270 : poisson_solver_stats_t* stats)
271 : {
272 18 : (void)x_temp; /* BiCGSTAB doesn't use the temp buffer */
273 :
274 18 : bicgstab_context_t* ctx = (bicgstab_context_t*)solver->context;
275 18 : size_t nx = solver->nx;
276 18 : size_t ny = solver->ny;
277 18 : double dx2 = ctx->dx2;
278 18 : double dy2 = ctx->dy2;
279 18 : size_t stride_z = ctx->stride_z;
280 18 : size_t k_start = ctx->k_start;
281 18 : size_t k_end = ctx->k_end;
282 18 : double inv_dz2 = ctx->inv_dz2;
283 :
284 18 : double* r = ctx->r;
285 18 : double* r_hat = ctx->r_hat;
286 18 : double* p = ctx->p;
287 18 : double* v = ctx->v;
288 18 : double* s = ctx->s;
289 18 : double* t = ctx->t;
290 :
291 18 : poisson_solver_params_t* params = &solver->params;
292 18 : double start_time = poisson_solver_get_time_ms();
293 :
294 : /* Not poisson_solver_apply_bc: the initial residual has to see the same walls
295 : * the iteration below inverts. See poisson_solver_krylov_apply_bc. */
296 18 : poisson_solver_krylov_apply_bc(solver, x);
297 :
298 : /* Compute initial residual: r_0 = b - A*x_0 */
299 18 : compute_residual(x, rhs, r, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
300 :
301 : /* r_hat = r_0 (shadow residual) */
302 18 : copy_vector(r, r_hat, nx, ny, k_start, k_end, stride_z);
303 :
304 : /* Initialize: rho = alpha = omega = 1, v = p = 0 */
305 64 : double rho = 1.0;
306 64 : double alpha = 1.0;
307 64 : double omega = 1.0;
308 64 : zero_vector(v, nx, ny, k_start, k_end, stride_z);
309 64 : zero_vector(p, nx, ny, k_start, k_end, stride_z);
310 :
311 : /* Compute initial residual norm */
312 18 : double r_dot_r = dot_product(r, r, nx, ny, k_start, k_end, stride_z);
313 18 : double initial_res = sqrt(r_dot_r);
314 :
315 18 : if (stats) {
316 18 : stats->initial_residual = initial_res;
317 : }
318 :
319 : /* Check if already converged */
320 : /* Never below the round-off floor of the residual at the initial guess:
321 : * a warm start near steady state begins there (poisson_solver_residual_floor) */
322 18 : double floor_res = poisson_solver_residual_floor(solver, x, POISSON_NORM_L2);
323 18 : double tolerance = poisson_solver_stop_target(params, initial_res, floor_res);
324 :
325 34 : if (initial_res < poisson_solver_done_target(params, floor_res)) {
326 3 : if (stats) {
327 3 : stats->status = POISSON_CONVERGED;
328 3 : stats->iterations = 0;
329 3 : stats->final_residual = initial_res;
330 3 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
331 : }
332 3 : return CFD_SUCCESS;
333 : }
334 :
335 297 : int converged = 0;
336 : int iter;
337 : double res_norm = initial_res;
338 :
339 297 : for (iter = 0; iter < params->max_iterations; iter++) {
340 : /* rho_new = (r_hat, r) */
341 296 : double rho_new = dot_product(r_hat, r, nx, ny, k_start, k_end, stride_z);
342 :
343 : /* Check for breakdown */
344 296 : if (fabs(rho_new) < BICGSTAB_BREAKDOWN_THRESHOLD) {
345 0 : if (stats) {
346 0 : stats->status = POISSON_STAGNATED;
347 0 : stats->iterations = iter + 1;
348 0 : stats->final_residual = res_norm;
349 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
350 : }
351 0 : return CFD_ERROR_MAX_ITER;
352 : }
353 :
354 : /* beta = (rho_new / rho) * (alpha / omega) */
355 296 : double beta = (rho_new / rho) * (alpha / omega);
356 :
357 : /* p = r + beta * (p - omega * v) */
358 620 : for (size_t k = k_start; k < k_end; k++) {
359 9360 : for (size_t j = 1; j < ny - 1; j++) {
360 274032 : for (size_t i = 1; i < nx - 1; i++) {
361 264996 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
362 264996 : p[idx] = r[idx] + beta * (p[idx] - omega * v[idx]);
363 : }
364 : }
365 : }
366 :
367 : /* v = A * p */
368 : /* Homogeneous boundary condition on the direction: this is what makes the
369 : * apply below the operator the walls describe, and the direction is rebuilt
370 : * from interior-only updates, so it is stale otherwise. */
371 296 : poisson_solver_krylov_apply_bc_homogeneous(solver, p);
372 296 : apply_laplacian(p, v, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
373 :
374 : /* alpha = rho_new / (r_hat, v) */
375 296 : double r_hat_dot_v = dot_product(r_hat, v, nx, ny, k_start, k_end, stride_z);
376 :
377 : /* Check for breakdown */
378 296 : if (fabs(r_hat_dot_v) < BICGSTAB_BREAKDOWN_THRESHOLD) {
379 0 : if (stats) {
380 0 : stats->status = POISSON_STAGNATED;
381 0 : stats->iterations = iter + 1;
382 0 : stats->final_residual = res_norm;
383 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
384 : }
385 0 : return CFD_ERROR_MAX_ITER;
386 : }
387 :
388 296 : alpha = rho_new / r_hat_dot_v;
389 :
390 : /* s = r - alpha * v */
391 620 : for (size_t k = k_start; k < k_end; k++) {
392 9360 : for (size_t j = 1; j < ny - 1; j++) {
393 274032 : for (size_t i = 1; i < nx - 1; i++) {
394 264996 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
395 264996 : s[idx] = r[idx] - alpha * v[idx];
396 : }
397 : }
398 : }
399 :
400 : /* Check for early convergence on s */
401 296 : double s_norm = sqrt(dot_product(s, s, nx, ny, k_start, k_end, stride_z));
402 296 : if (s_norm < tolerance || s_norm < params->absolute_tolerance) {
403 : /* Update x and return */
404 15 : axpy(alpha, p, x, nx, ny, k_start, k_end, stride_z);
405 : res_norm = s_norm;
406 : converged = 1;
407 : break;
408 : }
409 :
410 : /* t = A * s */
411 289 : poisson_solver_krylov_apply_bc_homogeneous(solver, s);
412 289 : apply_laplacian(s, t, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
413 :
414 : /* omega = (t, s) / (t, t) */
415 867 : double t_dot_s = dot_product(t, s, nx, ny, k_start, k_end, stride_z);
416 289 : double t_dot_t = dot_product(t, t, nx, ny, k_start, k_end, stride_z);
417 :
418 : /* Check for breakdown */
419 289 : if (fabs(t_dot_t) < BICGSTAB_BREAKDOWN_THRESHOLD) {
420 : /* Update x with available progress */
421 0 : axpy(alpha, p, x, nx, ny, k_start, k_end, stride_z);
422 0 : if (stats) {
423 0 : stats->status = POISSON_STAGNATED;
424 0 : stats->iterations = iter + 1;
425 0 : stats->final_residual = s_norm;
426 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
427 : }
428 0 : return CFD_ERROR_MAX_ITER;
429 : }
430 :
431 289 : omega = t_dot_s / t_dot_t;
432 :
433 : /* x = x + alpha * p + omega * s */
434 578 : for (size_t k = k_start; k < k_end; k++) {
435 8752 : for (size_t j = 1; j < ny - 1; j++) {
436 263376 : for (size_t i = 1; i < nx - 1; i++) {
437 254913 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
438 254913 : x[idx] += alpha * p[idx] + omega * s[idx];
439 : }
440 : }
441 : }
442 :
443 : /* r = s - omega * t */
444 578 : for (size_t k = k_start; k < k_end; k++) {
445 8752 : for (size_t j = 1; j < ny - 1; j++) {
446 263376 : for (size_t i = 1; i < nx - 1; i++) {
447 254913 : size_t idx = (k * stride_z) + (IDX_2D(i, j, nx));
448 254913 : r[idx] = s[idx] - omega * t[idx];
449 : }
450 : }
451 : }
452 :
453 : /* Update rho for next iteration */
454 578 : rho = rho_new;
455 :
456 : /* Compute residual norm */
457 289 : res_norm = sqrt(dot_product(r, r, nx, ny, k_start, k_end, stride_z));
458 :
459 : /* Check convergence at intervals */
460 289 : if (iter % params->check_interval == 0) {
461 289 : if (params->verbose) {
462 0 : CFD_LOG_DEBUG("poisson", "BiCGSTAB Iter %d: residual = %.6e", iter, res_norm);
463 : }
464 :
465 289 : if (res_norm < tolerance || res_norm < params->absolute_tolerance) {
466 : converged = 1;
467 : break;
468 : }
469 : }
470 :
471 : /* Check for omega breakdown (would cause division by zero next iteration) */
472 282 : if (fabs(omega) < BICGSTAB_BREAKDOWN_THRESHOLD) {
473 0 : if (stats) {
474 0 : stats->status = POISSON_STAGNATED;
475 0 : stats->iterations = iter + 1;
476 0 : stats->final_residual = res_norm;
477 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
478 : }
479 0 : return CFD_ERROR_MAX_ITER;
480 : }
481 : }
482 :
483 : /* Final convergence check */
484 15 : if (!converged && (res_norm < tolerance || res_norm < params->absolute_tolerance)) {
485 14 : converged = 1;
486 : }
487 :
488 : /* Apply final boundary conditions */
489 15 : poisson_solver_apply_bc(solver, x);
490 :
491 15 : double end_time = poisson_solver_get_time_ms();
492 :
493 15 : if (stats) {
494 15 : stats->iterations = (iter < params->max_iterations) ? (iter + 1) : iter;
495 15 : stats->final_residual = res_norm;
496 15 : stats->elapsed_time_ms = end_time - start_time;
497 15 : stats->status = converged ? POISSON_CONVERGED : POISSON_MAX_ITER;
498 : }
499 :
500 15 : return converged ? CFD_SUCCESS : CFD_ERROR_MAX_ITER;
501 : }
502 :
503 : /**
504 : * Single iteration is not well-defined for BiCGSTAB as it maintains internal state.
505 : * We provide a minimal implementation that returns the current residual.
506 : */
507 0 : static cfd_status_t bicgstab_scalar_iterate(
508 : poisson_solver_t* solver,
509 : double* x,
510 : double* x_temp,
511 : const double* rhs,
512 : double* residual)
513 : {
514 0 : (void)x_temp;
515 :
516 : /* BiCGSTAB doesn't support single iteration mode well.
517 : * Return the current residual from the Laplacian. */
518 0 : if (residual) {
519 0 : *residual = poisson_solver_compute_residual(solver, x, rhs);
520 : }
521 0 : return CFD_SUCCESS;
522 : }
523 :
524 : /* ============================================================================
525 : * FACTORY FUNCTION
526 : * ============================================================================ */
527 :
528 26 : poisson_solver_t* create_bicgstab_scalar_solver(void) {
529 26 : poisson_solver_t* solver = (poisson_solver_t*)cfd_calloc(1, sizeof(poisson_solver_t));
530 26 : if (!solver) {
531 : return NULL;
532 : }
533 :
534 26 : solver->name = POISSON_SOLVER_TYPE_BICGSTAB_SCALAR;
535 26 : solver->description = "BiCGSTAB (scalar CPU)";
536 26 : solver->method = POISSON_METHOD_BICGSTAB;
537 26 : solver->backend = POISSON_BACKEND_SCALAR;
538 26 : solver->params = poisson_solver_params_default();
539 :
540 26 : solver->init = bicgstab_scalar_init;
541 26 : solver->destroy = bicgstab_scalar_destroy;
542 26 : solver->solve = bicgstab_scalar_solve; /* BiCGSTAB uses custom solve loop */
543 26 : solver->iterate = bicgstab_scalar_iterate;
544 26 : solver->apply_bc = NULL; /* Use default Neumann */
545 :
546 26 : return solver;
547 : }
|