xingo_sparse/error.rs
1//! # Chapter 5.0 — Errors
2//!
3//! ## Purpose
4//! Two kinds of failure are reported, never panicked on. The containers
5//! (Chapter 5.8) validate outside data — triplets, raw compressed arrays —
6//! and report the first violation found as a [`SparseError`], which names
7//! the offending array, position and value; every `check_invariants()` of
8//! the crate returns the same type. The factorization reports a singular
9//! basis, an inconsistent basis description, or an update called without
10//! its spike, as an [`LuError`] carrying what the caller needs to recover.
11//! Since L1.5 two more kinds join them: the symmetric (KKT) solvers of
12//! Chapter 5.14 report a [`KktError`] — structure, symmetry, a zero pivot
13//! or the wrong inertia (S6) — and the dense kernels of Chapter 5.16 a
14//! [`DenseError`].
15//!
16//! `xingo-core` converts both into its `CoreError` (`From` impls there):
17//! a [`SparseError`] maps variant by variant onto the `CoreError` that the
18//! first edition reported, so the messages the solver prints are
19//! unchanged.
20//!
21//! ## Invariants
22//! (E1) `Singular { rank_deficiency, cols, rows }` has
23//! `rank_deficiency = cols.len() = rows.len() ≥ 1`. Replacing, for
24//! every `k`, the basis column at position `cols[k]` by the logical
25//! column of row `rows[k]` yields a basis whose factorization succeeds
26//! (tested in Chapter 5.3); this is the classic basis repair of the
27//! simplex method (Koberstein 2005, §8.2.3; HiGHS
28//! `HFactor::buildSimple` rank deficiency handling).
29//! (E2) Errors are reported, never repaired silently: a constructor either
30//! returns a structure satisfying all of its invariants or an error.
31
32use std::fmt;
33
34use crate::Row;
35
36/// Structural error of the containers: invariants (C1)–(C4) of Chapter 5.8
37/// or (V1)–(V3) of Chapter 5.8.3 violated by the input, or the basis
38/// references of Chapter 5.1 out of range.
39///
40/// The `what` fields are short static descriptions of the offending array
41/// or quantity (for instance `"row index"` or `"value array"`).
42#[derive(Clone, Debug, PartialEq)]
43pub enum SparseError {
44 /// Two lengths that must agree do not.
45 Dimension {
46 /// Which array or dimension has the wrong length.
47 what: &'static str,
48 /// Expected length.
49 expected: usize,
50 /// Actual length.
51 found: usize,
52 },
53 /// An index is not smaller than the dimension it refers to.
54 IndexOutOfRange {
55 /// What kind of index was out of range.
56 what: &'static str,
57 /// The offending index.
58 index: usize,
59 /// The exclusive upper bound it violated.
60 bound: usize,
61 },
62 /// A stored value is not allowed (non-finite, or an explicit zero
63 /// where (C3) forbids it).
64 InvalidValue {
65 /// What the value represents.
66 what: &'static str,
67 /// Position of the value.
68 index: usize,
69 /// The offending value, as the nearest `f64`.
70 value: f64,
71 },
72 /// A dimension does not fit in the `u32` index space.
73 TooLarge {
74 /// What dimension overflowed.
75 what: &'static str,
76 /// The offending dimension.
77 value: usize,
78 },
79 /// Pointers not nondecreasing, indices not sorted, a pattern
80 /// inconsistent with its marks…; the message names the invariant.
81 Malformed(String),
82}
83
84impl fmt::Display for SparseError {
85 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
86 match self {
87 Self::IndexOutOfRange { what, index, bound } => {
88 write!(f, "{what} {index} out of bounds (must be < {bound})")
89 }
90 Self::Dimension {
91 what,
92 expected,
93 found,
94 } => {
95 write!(f, "{what} has length {found}, expected {expected}")
96 }
97 Self::InvalidValue { what, index, value } => {
98 write!(f, "invalid {what} at position {index}: {value}")
99 }
100 Self::TooLarge { what, value } => {
101 write!(f, "{what} = {value} exceeds the u32 index space")
102 }
103 Self::Malformed(msg) => write!(f, "invariant violated: {msg}"),
104 }
105 }
106}
107
108impl std::error::Error for SparseError {}
109
110/// Error raised by [`crate::LuFactor::factorize`] and
111/// [`crate::LuFactor::update`].
112#[derive(Clone, Debug, PartialEq)]
113pub enum LuError {
114 /// The basis is singular: no acceptable pivot (magnitude above
115 /// [`crate::LuOptions::abs_pivot_tol`]) exists for `rank_deficiency`
116 /// columns. `cols` lists their basis positions and `rows` the rows
117 /// left without a pivot, both in increasing order (invariant E1).
118 ///
119 /// After a failed factorization the factor is invalid until the next
120 /// successful one; after a failed update it still represents the
121 /// previous basis (Chapter 5.5).
122 Singular {
123 /// Number of dependent columns, `= cols.len() = rows.len()`.
124 rank_deficiency: usize,
125 /// Basis positions of the dependent columns.
126 cols: Vec<usize>,
127 /// Rows left without a pivot.
128 rows: Vec<Row>,
129 },
130 /// The basis references do not fit the matrix (Chapter 5.1, B1), or a
131 /// position is out of range.
132 Structure(SparseError),
133 /// [`crate::LuFactor::update`] was called without a spike recorded by
134 /// [`crate::LuFactor::ftran_for_update`] since the last change of the
135 /// factor.
136 NoSpike,
137 /// A solve or an update was requested from a factor that does not hold
138 /// a valid factorization (never factorized, or the last factorization
139 /// failed).
140 NotFactorized,
141}
142
143impl fmt::Display for LuError {
144 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
145 match self {
146 Self::Singular {
147 rank_deficiency,
148 cols,
149 ..
150 } => write!(
151 f,
152 "singular basis: rank deficiency {rank_deficiency} (positions {cols:?})"
153 ),
154 Self::Structure(e) => write!(f, "invalid basis: {e}"),
155 Self::NoSpike => write!(f, "update called without a spike from ftran_for_update"),
156 Self::NotFactorized => write!(f, "the factor holds no valid factorization"),
157 }
158 }
159}
160
161impl std::error::Error for LuError {
162 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
163 match self {
164 Self::Structure(e) => Some(e),
165 _ => None,
166 }
167 }
168}
169
170impl From<SparseError> for LuError {
171 fn from(e: SparseError) -> Self {
172 Self::Structure(e)
173 }
174}
175
176/// Error raised by a [`crate::KktSolver`] (Chapter 5.14).
177///
178/// As in [`LuError`], structural problems of the input are reported in a
179/// [`KktError::Structure`] carrying the [`SparseError`] of the container
180/// check, so `Eq` is not derived (the [`SparseError::InvalidValue`]
181/// variant holds an `f64`).
182#[derive(Clone, Debug, PartialEq)]
183pub enum KktError {
184 /// The pattern is not square, or it stores entries on both sides of
185 /// the diagonal without being structurally symmetric (invariant (K1)
186 /// of Chapter 5.14).
187 NotSymmetric,
188 /// A pivot of the factorization is exactly zero (or not finite) and no
189 /// dynamic regularization was asked for (or it could not lift it);
190 /// `position` is the row of `K` (original numbering) whose pivot
191 /// failed.
192 ZeroPivot {
193 /// Row of `K`, in the caller's numbering.
194 position: usize,
195 },
196 /// The factorization produced a NaN or an infinity (an overflow of the
197 /// elimination; step K3′ and invariant (S10) of Chapter 5.14);
198 /// `position` is the row of `K` (original numbering) of the first
199 /// column of the factor holding one.
200 NotFinite {
201 /// Row of `K`, in the caller's numbering.
202 position: usize,
203 },
204 /// The inertia of the factorization differs from the one the form
205 /// requires (invariant (S6)).
206 WrongInertia {
207 /// The inertia of the computed factorization.
208 found: crate::Inertia,
209 /// The inertia [`crate::KktForm`] requires.
210 expected: crate::Inertia,
211 },
212 /// The matrix does not satisfy the container invariants (S1), its
213 /// dimensions do not match the form or the analysis, or its lower
214 /// triangle has an entry outside the analyzed pattern.
215 Structure(SparseError),
216 /// The backend ran out of memory or refused the problem.
217 Backend(&'static str),
218}
219
220impl fmt::Display for KktError {
221 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
222 match self {
223 Self::NotSymmetric => write!(f, "the KKT pattern is not square and symmetric"),
224 Self::ZeroPivot { position } => write!(f, "zero pivot at row {position}"),
225 Self::NotFinite { position } => {
226 write!(f, "non-finite factor (overflow) at row {position}")
227 }
228 Self::WrongInertia { found, expected } => write!(
229 f,
230 "wrong inertia: found ({}, {}, {}), expected ({}, {}, {})",
231 found.positive,
232 found.negative,
233 found.zero,
234 expected.positive,
235 expected.negative,
236 expected.zero
237 ),
238 Self::Structure(e) => write!(f, "invalid KKT matrix: {e}"),
239 Self::Backend(what) => write!(f, "KKT backend failure: {what}"),
240 }
241 }
242}
243
244impl std::error::Error for KktError {
245 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
246 match self {
247 Self::Structure(e) => Some(e),
248 _ => None,
249 }
250 }
251}
252
253impl From<SparseError> for KktError {
254 fn from(e: SparseError) -> Self {
255 Self::Structure(e)
256 }
257}
258
259/// Error raised by a [`crate::DenseKernel`] (Chapter 5.16).
260#[derive(Clone, Debug, PartialEq, Eq)]
261pub enum DenseError {
262 /// The block is not positive definite: the pivot of column `position`
263 /// is not positive (or not finite).
264 NotPositiveDefinite {
265 /// Column whose pivot failed.
266 position: usize,
267 },
268 /// The dimensions of the blocks do not agree (or a block that must be
269 /// square is not).
270 Dimension,
271}
272
273impl fmt::Display for DenseError {
274 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
275 match self {
276 Self::NotPositiveDefinite { position } => {
277 write!(f, "block not positive definite at column {position}")
278 }
279 Self::Dimension => write!(f, "block dimensions do not agree"),
280 }
281 }
282}
283
284impl std::error::Error for DenseError {}