cartan_mimetic/lib.rs
1//! Mimetic Hodge stars for compatible discretisation.
2//!
3//! A compatible discretisation represents the exterior derivative exactly, the
4//! coboundary being combinatorial and satisfying `d d = 0` identically, and puts
5//! every metric quantity into the inner product on k-cochains. That inner
6//! product is the only choice the method makes, since the codifferential is its
7//! adjoint,
8//!
9//! ```text
10//! delta_k = M_{k-1}^-1 d_{k-1}^T M_k Laplacian = d delta + delta d
11//! ```
12//!
13//! and the Laplacian follows. This crate builds `M_k` on one simplex.
14//!
15//! # What a star has to satisfy
16//!
17//! **Consistency**: the discrete inner product reproduces the exact one whenever
18//! both arguments are constant k-forms on the cell. Writing `N` for the degrees
19//! of freedom of a basis of those forms, one row per k-face, and `G` for their
20//! exact Gram matrix, that is `N^T M N = G`.
21//!
22//! **Stability**: `M` is positive definite, and spectrally equivalent to its own
23//! diagonal, so the conditioning does not degrade under refinement.
24//!
25//! # Why the diagonal answer is not always available
26//!
27//! A diagonal star has one unknown per k-face and consistency imposes one
28//! equation per symmetric pair of constant forms:
29//!
30//! ```text
31//! unknowns = C(n+1, k+1) k-faces of an n-simplex
32//! equations = C(n,k) (C(n,k) + 1) / 2 symmetric entries of G
33//! ```
34//!
35//! which decides the question before any geometry enters:
36//!
37//! | n | k | unknowns | equations | diagonal star |
38//! |---|---|----------|-----------|---------------|
39//! | 2 | 0 | 3 | 1 | a 2-parameter family |
40//! | 2 | 1 | 3 | 3 | unique, and equal to `cot/2` |
41//! | 3 | 0 | 4 | 1 | a 3-parameter family |
42//! | 3 | 1 | 6 | 6 | unique, sign not guaranteed |
43//! | 3 | 2 | 4 | 6 | overdetermined, generically none |
44//!
45//! Two consequences, each measured in the tests beside this file. At
46//! `n = 2, k = 1` the unique diagonal star turns negative exactly when the
47//! triangle is obtuse, so consistency, diagonality and positivity cannot hold at
48//! once. At `n = 3, k = 2` no diagonal star is consistent on a general
49//! tetrahedron at all, and at `n = 3, k = 1` the unique one is negative on every
50//! tetrahedron of a subdivided cube, which is the ordinary way to mesh a box.
51//!
52//! Giving up diagonality restores both properties, which is what this crate
53//! does. [`local_star`] is consistent to machine precision and
54//! positive definite on every simplex tested, slivers, needles and caps
55//! included.
56
57use nalgebra::{DMatrix, DVector};
58
59mod assemble;
60mod combinatorics;
61mod local;
62
63pub use assemble::{Mesh, assemble_star};
64pub use combinatorics::{k_faces, n_choose_k};
65pub use local::{DiagonalStar, Simplex, diagonal_star, local_star};
66
67/// The consistency data of one simplex at one form degree.
68///
69/// `dofs` lists the degrees of freedom of a basis of constant k-forms, one row
70/// per k-face and one column per basis form, and `gram` their exact inner
71/// products. A star `M` is consistent exactly when `dofs^T M dofs == gram`.
72#[derive(Debug, Clone)]
73pub struct Consistency {
74 /// One row per k-face of the simplex, one column per constant k-form.
75 pub dofs: DMatrix<f64>,
76 /// The exact Gram matrix of those forms over the simplex.
77 pub gram: DMatrix<f64>,
78}
79
80impl Consistency {
81 /// How far a candidate star is from consistent, relative to the cell volume.
82 ///
83 /// Zero to rounding is the only acceptable answer. This is the check to
84 /// apply to any star from anywhere, including one this crate did not build.
85 pub fn residual(&self, star: &DMatrix<f64>) -> f64 {
86 let scale = self.gram.diagonal().iter().cloned().fold(0.0_f64, f64::max);
87 if scale <= 0.0 {
88 return 0.0;
89 }
90 (&self.dofs.transpose() * star * &self.dofs - &self.gram)
91 .abs()
92 .max()
93 / scale
94 }
95
96 /// The least-squares diagonal star, and its consistency residual.
97 ///
98 /// The residual is zero where a consistent diagonal star exists and positive
99 /// where the system is overdetermined, which is what the table above
100 /// predicts and what makes this a usable test rather than a guess.
101 pub fn best_diagonal(&self) -> (DVector<f64>, f64) {
102 // Each equation is one symmetric entry of `dofs^T D dofs`.
103 let m = self.gram.nrows();
104 let faces = self.dofs.nrows();
105 let mut rows = Vec::new();
106 let mut rhs = Vec::new();
107 for a in 0..m {
108 for b in a..m {
109 rows.push(
110 (0..faces)
111 .map(|f| self.dofs[(f, a)] * self.dofs[(f, b)])
112 .collect::<Vec<_>>(),
113 );
114 rhs.push(self.gram[(a, b)]);
115 }
116 }
117 let lhs = DMatrix::from_fn(rows.len(), faces, |i, j| rows[i][j]);
118 let rhs = DVector::from_vec(rhs);
119 // Normal equations, which is enough at these sizes and keeps the
120 // dependency surface to nalgebra's dense core.
121 let ata = lhs.transpose() * &lhs;
122 let atb = lhs.transpose() * &rhs;
123 let d = ata
124 .clone()
125 .svd(true, true)
126 .solve(&atb, 1e-12)
127 .unwrap_or_else(|_| DVector::zeros(faces));
128 let scale = self.gram.diagonal().iter().cloned().fold(0.0_f64, f64::max);
129 let residual = if scale > 0.0 {
130 (&lhs * &d - &rhs).abs().max() / scale
131 } else {
132 0.0
133 };
134 (d, residual)
135 }
136}