Skip to main content

neco_linear_exact/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2#![forbid(unsafe_code)]
3#![doc = include_str!("../README.md")]
4
5extern crate alloc;
6#[cfg(test)]
7extern crate std;
8
9use alloc::boxed::Box;
10use alloc::vec::Vec;
11use core::fmt;
12#[cfg(test)]
13std::thread_local! {
14    static INJECT_NEXT_ALLOCATION_FAILURE: core::cell::Cell<bool> = const { core::cell::Cell::new(false) };
15}
16
17use neco_algnum::{AlgnumError, RealAlgebraic};
18use neco_bigint::{BigInt, BigintError, Dyadic, ReducedRational};
19use neco_expr::{
20    project_exact_value_f64, AbsoluteBits, CertifiedF64Bundle, CertifiedF64Expression,
21    CertifiedScalarProjection, ComputationProductId, ConsumerId, ExactComputationProduct,
22    ExactValue, ExprId, FailureLocation, FailureOperation, MatrixInputMismatchField,
23    MatrixInputMismatchPayload, MatrixInputRole, NecoFailure, NecoImplementationSource, OwnerId,
24    ProjectionPolicy, ProvenanceMismatchField, ProvenanceMismatchPayload, ProvenanceRecord,
25    ScalarProjectionError, StorageFailurePayload,
26};
27use neco_formsum::{FormSum, FormSumErrorKind};
28use neco_linear_dense::DenseMatrix;
29use neco_linear_types::{ColumnIndex, LinearError, RowIndex, Shape, Vector};
30
31#[derive(Debug, Eq, PartialEq)]
32pub enum ExactLinearError {
33    Linear(LinearError),
34    Bigint(BigintError),
35    FormSum(FormSumErrorKind),
36    Algnum(AlgnumError),
37    NonSquareMatrix { rows: usize, columns: usize },
38}
39
40impl fmt::Display for ExactLinearError {
41    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
42        match self {
43            Self::Linear(error) => error.fmt(formatter),
44            Self::Bigint(error) => error.fmt(formatter),
45            Self::FormSum(error) => error.fmt(formatter),
46            Self::Algnum(error) => error.fmt(formatter),
47            Self::NonSquareMatrix { rows, columns } => {
48                write!(
49                    formatter,
50                    "determinant requires a square matrix, got {rows}x{columns}"
51                )
52            }
53        }
54    }
55}
56
57#[cfg(feature = "std")]
58impl std::error::Error for ExactLinearError {}
59
60impl From<LinearError> for ExactLinearError {
61    fn from(error: LinearError) -> Self {
62        Self::Linear(error)
63    }
64}
65
66impl From<BigintError> for ExactLinearError {
67    fn from(error: BigintError) -> Self {
68        Self::Bigint(error)
69    }
70}
71
72impl From<FormSumErrorKind> for ExactLinearError {
73    fn from(error: FormSumErrorKind) -> Self {
74        Self::FormSum(error)
75    }
76}
77
78impl From<AlgnumError> for ExactLinearError {
79    fn from(error: AlgnumError) -> Self {
80        Self::Algnum(error)
81    }
82}
83
84#[derive(Debug, Eq, PartialEq)]
85pub enum CertifiedLinearProjectionError {
86    Exact(ExactLinearError),
87    VectorElement {
88        index: usize,
89        source: ScalarProjectionError,
90    },
91    MatrixElement {
92        row: usize,
93        column: usize,
94        source: ScalarProjectionError,
95    },
96    Linear(LinearError),
97    Bigint(BigintError),
98}
99
100impl fmt::Display for CertifiedLinearProjectionError {
101    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
102        match self {
103            Self::Exact(error) => error.fmt(formatter),
104            Self::VectorElement { index, source } => {
105                write!(
106                    formatter,
107                    "vector projection failed at index {index}: {source}"
108                )
109            }
110            Self::MatrixElement {
111                row,
112                column,
113                source,
114            } => write!(
115                formatter,
116                "matrix projection failed at row {row}, column {column}: {source}"
117            ),
118            Self::Linear(error) => error.fmt(formatter),
119            Self::Bigint(error) => error.fmt(formatter),
120        }
121    }
122}
123
124#[cfg(feature = "std")]
125impl std::error::Error for CertifiedLinearProjectionError {}
126
127impl From<ExactLinearError> for CertifiedLinearProjectionError {
128    fn from(error: ExactLinearError) -> Self {
129        Self::Exact(error)
130    }
131}
132
133impl From<LinearError> for CertifiedLinearProjectionError {
134    fn from(error: LinearError) -> Self {
135        Self::Linear(error)
136    }
137}
138
139impl From<BigintError> for CertifiedLinearProjectionError {
140    fn from(error: BigintError) -> Self {
141        Self::Bigint(error)
142    }
143}
144
145pub trait CertifiedF64Scalar {
146    fn project_f64_scalar(
147        &self,
148        policy: ProjectionPolicy,
149    ) -> Result<CertifiedScalarProjection, ScalarProjectionError>;
150}
151
152impl CertifiedF64Scalar for ReducedRational {
153    fn project_f64_scalar(
154        &self,
155        policy: ProjectionPolicy,
156    ) -> Result<CertifiedScalarProjection, ScalarProjectionError> {
157        let value =
158            RealAlgebraic::from_reduced_rational(self).map_err(ScalarProjectionError::Algnum)?;
159        project_exact_value_f64(&ExactValue::Algebraic(value), policy)
160    }
161}
162
163impl CertifiedF64Scalar for FormSum {
164    fn project_f64_scalar(
165        &self,
166        policy: ProjectionPolicy,
167    ) -> Result<CertifiedScalarProjection, ScalarProjectionError> {
168        project_exact_value_f64(
169            &ExactValue::FormSum(self.try_clone().map_err(|error| match error {
170                FormSumErrorKind::Bigint(error) => ScalarProjectionError::Bigint(error),
171                error => ScalarProjectionError::Algnum(AlgnumError::FormSum(error)),
172            })?),
173            policy,
174        )
175    }
176}
177
178impl CertifiedF64Scalar for RealAlgebraic {
179    fn project_f64_scalar(
180        &self,
181        policy: ProjectionPolicy,
182    ) -> Result<CertifiedScalarProjection, ScalarProjectionError> {
183        project_exact_value_f64(
184            &ExactValue::Algebraic(self.try_clone().map_err(ScalarProjectionError::Algnum)?),
185            policy,
186        )
187    }
188}
189
190#[derive(Debug, PartialEq)]
191pub struct CertifiedVectorProjection {
192    policy: ProjectionPolicy,
193    values: Vector<f64>,
194    certificates: Vec<CertifiedScalarProjection>,
195    absolute_error_bound: Dyadic,
196}
197
198impl CertifiedVectorProjection {
199    pub const fn policy(&self) -> ProjectionPolicy {
200        self.policy
201    }
202
203    pub fn values(&self) -> &Vector<f64> {
204        &self.values
205    }
206
207    pub fn certificates(&self) -> &[CertifiedScalarProjection] {
208        &self.certificates
209    }
210
211    pub fn absolute_error_bound(&self) -> &Dyadic {
212        &self.absolute_error_bound
213    }
214}
215
216#[derive(Debug, PartialEq)]
217pub struct CertifiedMatrixProjection {
218    policy: ProjectionPolicy,
219    matrix: DenseMatrix<f64>,
220    certificates_row_major: Vec<CertifiedScalarProjection>,
221    absolute_error_bound: Dyadic,
222}
223
224impl CertifiedMatrixProjection {
225    pub const fn policy(&self) -> ProjectionPolicy {
226        self.policy
227    }
228
229    pub fn matrix(&self) -> &DenseMatrix<f64> {
230        &self.matrix
231    }
232
233    pub fn certificates_row_major(&self) -> &[CertifiedScalarProjection] {
234        &self.certificates_row_major
235    }
236
237    pub fn absolute_error_bound(&self) -> &Dyadic {
238        &self.absolute_error_bound
239    }
240
241    pub fn certificate(
242        &self,
243        row: RowIndex,
244        column: ColumnIndex,
245    ) -> Result<&CertifiedScalarProjection, CertifiedLinearProjectionError> {
246        let shape = self.matrix.shape();
247        if row.value() >= shape.rows() {
248            return Err(LinearError::IndexOutOfBounds {
249                axis: "row",
250                index: row.value(),
251                bound: shape.rows(),
252            }
253            .into());
254        }
255        if column.value() >= shape.columns() {
256            return Err(LinearError::IndexOutOfBounds {
257                axis: "column",
258                index: column.value(),
259                bound: shape.columns(),
260            }
261            .into());
262        }
263        let index = row
264            .value()
265            .checked_mul(shape.columns())
266            .and_then(|offset| offset.checked_add(column.value()))
267            .ok_or(LinearError::CapacityOverflow {
268                requested: usize::MAX,
269            })?;
270        self.certificates_row_major.get(index).ok_or(
271            LinearError::InvalidStorage {
272                reason: "matrix certificate storage is shorter than its declared shape",
273            }
274            .into(),
275        )
276    }
277}
278pub trait MatrixIndex {
279    fn value(self) -> usize;
280}
281
282impl MatrixIndex for usize {
283    fn value(self) -> usize {
284        self
285    }
286}
287
288impl MatrixIndex for RowIndex {
289    fn value(self) -> usize {
290        RowIndex::value(self)
291    }
292}
293
294impl MatrixIndex for ColumnIndex {
295    fn value(self) -> usize {
296        ColumnIndex::value(self)
297    }
298}
299#[derive(Debug, PartialEq)]
300pub struct CertifiedMatrixEntry<'a> {
301    row: usize,
302    column: usize,
303    expression: ExprId,
304    value: &'a CertifiedF64Expression,
305}
306
307impl CertifiedMatrixEntry<'_> {
308    pub const fn row(&self) -> usize {
309        self.row
310    }
311
312    pub const fn column(&self) -> usize {
313        self.column
314    }
315
316    pub const fn expression(&self) -> ExprId {
317        self.expression
318    }
319
320    pub const fn owner(&self) -> OwnerId {
321        self.value.owner()
322    }
323
324    pub const fn consumer_id(&self) -> ConsumerId {
325        self.value.consumer_id()
326    }
327
328    pub const fn precision(&self) -> AbsoluteBits {
329        self.value.precision()
330    }
331
332    pub const fn source(&self) -> NecoImplementationSource {
333        self.value.source()
334    }
335
336    pub fn certified(&self) -> &neco_expr::CertifiedF64 {
337        self.value.certified()
338    }
339
340    pub fn value(&self) -> f64 {
341        self.certified().value()
342    }
343
344    pub fn enclosure(&self) -> &neco_bigint::DyadicEnclosure {
345        self.certified().enclosure()
346    }
347
348    pub fn absolute_error_bound(&self) -> &Dyadic {
349        self.certified().absolute_error()
350    }
351}
352
353#[derive(Debug, PartialEq)]
354pub struct CertifiedMatrixInput {
355    matrix: DenseMatrix<f64>,
356    projection: CertifiedF64Bundle,
357    entry_expressions: Vec<ExprId>,
358    product_identity: ComputationProductId,
359    absolute_error_bound: Dyadic,
360}
361
362impl CertifiedMatrixInput {
363    pub fn from_product_projection<E>(
364        product: &ExactComputationProduct,
365        projection: &CertifiedF64Bundle,
366        matrix: DenseMatrix<f64>,
367        entry_expressions: E,
368        owner: OwnerId,
369        consumer: ConsumerId,
370    ) -> Result<Self, NecoFailure>
371    where
372        E: Into<Vec<ExprId>>,
373    {
374        let entry_expressions = entry_expressions.into();
375        let shape = matrix.shape();
376        let first_matrix_location = if shape.rows() > 0 && shape.columns() > 0 {
377            Some((0, 0))
378        } else {
379            None
380        };
381        let product_identity = product.product_identity().clone();
382        let expected_bundle = product.certified_descent(owner, consumer);
383        let expected_precision = expected_bundle
384            .map(CertifiedF64Bundle::precision)
385            .unwrap_or_else(|| projection.precision());
386        let expected_source = expected_bundle
387            .map(CertifiedF64Bundle::source)
388            .unwrap_or_else(|| projection.source());
389        let expected = matrix_provenance(
390            owner,
391            consumer,
392            expected_precision,
393            expected_source,
394            &product_identity,
395        );
396        let actual = matrix_provenance(
397            projection.owner(),
398            projection.consumer_id(),
399            projection.precision(),
400            projection.source(),
401            projection.product_identity(),
402        );
403        if let Some(field) = provenance_mismatch_field(&expected, &actual) {
404            return Err(NecoFailure::ProvenanceMismatch {
405                location: matrix_location(MatrixInputRole::Matrix, consumer, first_matrix_location),
406                payload: Box::new(ProvenanceMismatchPayload::new(field, expected, actual)),
407            });
408        }
409
410        let expected_count = shape.element_count().map_err(|_| {
411            matrix_mismatch(
412                matrix_location(MatrixInputRole::Matrix, consumer, None),
413                MatrixInputMismatchField::Shape,
414                expected.clone(),
415                actual.clone(),
416            )
417        })?;
418        if entry_expressions.len() < expected_count {
419            return Err(matrix_mismatch(
420                matrix_location(MatrixInputRole::Matrix, consumer, None),
421                MatrixInputMismatchField::MissingExpression,
422                expected.clone(),
423                actual.clone(),
424            ));
425        }
426        if entry_expressions.len() > expected_count {
427            return Err(matrix_mismatch(
428                matrix_location(MatrixInputRole::Matrix, consumer, None),
429                MatrixInputMismatchField::ExtraExpression,
430                expected.clone(),
431                actual.clone(),
432            ));
433        }
434        if projection.values().len() < expected_count {
435            return Err(matrix_mismatch(
436                matrix_location(MatrixInputRole::Matrix, consumer, None),
437                MatrixInputMismatchField::MissingExpression,
438                expected.clone(),
439                actual.clone(),
440            ));
441        }
442        if projection.values().len() > expected_count {
443            return Err(matrix_mismatch(
444                matrix_location(MatrixInputRole::Matrix, consumer, None),
445                MatrixInputMismatchField::ExtraExpression,
446                expected.clone(),
447                actual.clone(),
448            ));
449        }
450
451        for (index, expression) in entry_expressions.iter().copied().enumerate() {
452            if entry_expressions[..index].contains(&expression) {
453                let (row, column) = row_column(shape, index);
454                return Err(matrix_mismatch_with_details(
455                    matrix_location(MatrixInputRole::Matrix, consumer, Some((row, column))),
456                    MatrixInputMismatchField::DuplicateExpression,
457                    expected.clone(),
458                    actual.clone(),
459                    MismatchDetails {
460                        expected_expr: Some(expression),
461                        actual_expr: Some(expression),
462                        ..Default::default()
463                    },
464                ));
465            }
466        }
467
468        let mut absolute_error_bound = Dyadic::from_f64_exact(0.0)
469            .map_err(|error| storage_failure(MatrixInputRole::Matrix, consumer, error))?;
470        for (index, expression) in entry_expressions.iter().copied().enumerate() {
471            let (row, column) = row_column(shape, index);
472            let location = matrix_location(MatrixInputRole::Matrix, consumer, Some((row, column)));
473            let Some(value) = projection.values().get(index) else {
474                return Err(matrix_mismatch_with_details(
475                    location,
476                    MatrixInputMismatchField::MissingExpression,
477                    expected.clone(),
478                    actual.clone(),
479                    MismatchDetails {
480                        expected_expr: Some(expression),
481                        ..Default::default()
482                    },
483                ));
484            };
485            if value.expr() != expression {
486                return Err(matrix_mismatch_with_details(
487                    location,
488                    MatrixInputMismatchField::Expression,
489                    expected.clone(),
490                    actual.clone(),
491                    MismatchDetails {
492                        expected_expr: Some(expression),
493                        actual_expr: Some(value.expr()),
494                        ..Default::default()
495                    },
496                ));
497            }
498            let matching = projection
499                .values()
500                .iter()
501                .filter(|candidate| candidate.expr() == expression)
502                .count();
503            if matching > 1 {
504                return Err(matrix_mismatch_with_details(
505                    location,
506                    MatrixInputMismatchField::DuplicateExpression,
507                    expected.clone(),
508                    actual.clone(),
509                    MismatchDetails {
510                        expected_expr: Some(expression),
511                        actual_expr: Some(expression),
512                        ..Default::default()
513                    },
514                ));
515            }
516            if matching == 0 {
517                return Err(matrix_mismatch_with_details(
518                    location,
519                    MatrixInputMismatchField::MissingExpression,
520                    expected.clone(),
521                    actual.clone(),
522                    MismatchDetails {
523                        expected_expr: Some(expression),
524                        ..Default::default()
525                    },
526                ));
527            }
528            let row_index = shape.row_index(row).map_err(|_| {
529                matrix_mismatch(
530                    location,
531                    MatrixInputMismatchField::Shape,
532                    expected.clone(),
533                    actual.clone(),
534                )
535            })?;
536            let column_index = shape.column_index(column).map_err(|_| {
537                matrix_mismatch(
538                    location,
539                    MatrixInputMismatchField::Shape,
540                    expected.clone(),
541                    actual.clone(),
542                )
543            })?;
544            let matrix_value = *matrix.value(row_index, column_index).map_err(|_| {
545                matrix_mismatch(
546                    location,
547                    MatrixInputMismatchField::Shape,
548                    expected.clone(),
549                    actual.clone(),
550                )
551            })?;
552            let certified_bits = value.certified().value().to_bits();
553            let matrix_bits = matrix_value.to_bits();
554            if certified_bits != matrix_bits {
555                return Err(matrix_mismatch_with_details(
556                    location,
557                    MatrixInputMismatchField::NumericValue,
558                    expected.clone(),
559                    actual.clone(),
560                    MismatchDetails {
561                        expected_expr: Some(expression),
562                        actual_expr: Some(value.expr()),
563                        expected_bits: Some(certified_bits),
564                        actual_bits: Some(matrix_bits),
565                    },
566                ));
567            }
568            absolute_error_bound = absolute_error_bound
569                .add(value.certified().absolute_error())
570                .map_err(|error| storage_failure(MatrixInputRole::Matrix, consumer, error))?;
571        }
572        for (index, value) in projection.values().iter().enumerate() {
573            if !entry_expressions.contains(&value.expr()) {
574                let (row, column) = row_column(shape, index);
575                return Err(matrix_mismatch_with_details(
576                    matrix_location(MatrixInputRole::Matrix, consumer, Some((row, column))),
577                    MatrixInputMismatchField::ExtraExpression,
578                    expected.clone(),
579                    actual.clone(),
580                    MismatchDetails {
581                        actual_expr: Some(value.expr()),
582                        ..Default::default()
583                    },
584                ));
585            }
586        }
587
588        Ok(Self {
589            matrix,
590            projection: projection.try_clone()?,
591            entry_expressions,
592            product_identity,
593            absolute_error_bound,
594        })
595    }
596
597    pub fn matrix(&self) -> &DenseMatrix<f64> {
598        &self.matrix
599    }
600
601    pub fn shape(&self) -> Shape {
602        self.matrix.shape()
603    }
604
605    pub fn projection(&self) -> &CertifiedF64Bundle {
606        &self.projection
607    }
608
609    pub fn entry_expressions(&self) -> &[ExprId] {
610        &self.entry_expressions
611    }
612
613    pub const fn owner(&self) -> OwnerId {
614        self.projection.owner()
615    }
616
617    pub const fn consumer_id(&self) -> ConsumerId {
618        self.projection.consumer_id()
619    }
620
621    pub const fn precision(&self) -> AbsoluteBits {
622        self.projection.precision()
623    }
624
625    pub const fn source(&self) -> NecoImplementationSource {
626        self.projection.source()
627    }
628
629    pub fn product_identity(&self) -> &ComputationProductId {
630        &self.product_identity
631    }
632
633    pub fn absolute_error_bound(&self) -> &Dyadic {
634        &self.absolute_error_bound
635    }
636
637    pub fn entry<R: MatrixIndex, C: MatrixIndex>(
638        &self,
639        row: R,
640        column: C,
641    ) -> Result<CertifiedMatrixEntry<'_>, NecoFailure> {
642        let row = row.value();
643        let column = column.value();
644        let shape = self.matrix.shape();
645        let Some(index) = row
646            .checked_mul(shape.columns())
647            .and_then(|offset| offset.checked_add(column))
648            .filter(|_| row < shape.rows() && column < shape.columns())
649        else {
650            return Err(matrix_mismatch(
651                matrix_location(
652                    MatrixInputRole::Matrix,
653                    self.consumer_id(),
654                    Some((row, column)),
655                ),
656                MatrixInputMismatchField::Shape,
657                matrix_provenance(
658                    self.owner(),
659                    self.consumer_id(),
660                    self.precision(),
661                    self.source(),
662                    self.product_identity(),
663                ),
664                matrix_provenance(
665                    self.owner(),
666                    self.consumer_id(),
667                    self.precision(),
668                    self.source(),
669                    self.product_identity(),
670                ),
671            ));
672        };
673        let expression = *self.entry_expressions.get(index).ok_or_else(|| {
674            matrix_mismatch(
675                matrix_location(
676                    MatrixInputRole::Matrix,
677                    self.consumer_id(),
678                    Some((row, column)),
679                ),
680                MatrixInputMismatchField::MissingExpression,
681                matrix_provenance(
682                    self.owner(),
683                    self.consumer_id(),
684                    self.precision(),
685                    self.source(),
686                    self.product_identity(),
687                ),
688                matrix_provenance(
689                    self.owner(),
690                    self.consumer_id(),
691                    self.precision(),
692                    self.source(),
693                    self.product_identity(),
694                ),
695            )
696        })?;
697        let value = self
698            .projection
699            .values()
700            .iter()
701            .find(|value| value.expr() == expression)
702            .ok_or_else(|| {
703                matrix_mismatch_with_details(
704                    matrix_location(
705                        MatrixInputRole::Matrix,
706                        self.consumer_id(),
707                        Some((row, column)),
708                    ),
709                    MatrixInputMismatchField::MissingExpression,
710                    matrix_provenance(
711                        self.owner(),
712                        self.consumer_id(),
713                        self.precision(),
714                        self.source(),
715                        self.product_identity(),
716                    ),
717                    matrix_provenance(
718                        self.owner(),
719                        self.consumer_id(),
720                        self.precision(),
721                        self.source(),
722                        self.product_identity(),
723                    ),
724                    MismatchDetails {
725                        expected_expr: Some(expression),
726                        ..Default::default()
727                    },
728                )
729            })?;
730        Ok(CertifiedMatrixEntry {
731            row,
732            column,
733            expression,
734            value,
735        })
736    }
737}
738
739#[derive(Clone, Copy, Debug, Eq, PartialEq)]
740pub enum MassNormalizationMethod {
741    Identity,
742    PositiveDefiniteCholesky,
743}
744
745#[derive(Debug, PartialEq)]
746pub struct MassNormalizationReference {
747    matrix: CertifiedMatrixInput,
748    method: MassNormalizationMethod,
749}
750
751impl MassNormalizationReference {
752    pub fn new(
753        matrix: CertifiedMatrixInput,
754        method: MassNormalizationMethod,
755    ) -> Result<Self, NecoFailure> {
756        Ok(Self { matrix, method })
757    }
758
759    pub fn identity(matrix: CertifiedMatrixInput) -> Self {
760        Self {
761            matrix,
762            method: MassNormalizationMethod::Identity,
763        }
764    }
765
766    pub fn positive_definite_cholesky(matrix: CertifiedMatrixInput) -> Self {
767        Self {
768            matrix,
769            method: MassNormalizationMethod::PositiveDefiniteCholesky,
770        }
771    }
772
773    pub fn matrix(&self) -> &CertifiedMatrixInput {
774        &self.matrix
775    }
776
777    pub const fn method(&self) -> MassNormalizationMethod {
778        self.method
779    }
780
781    pub fn product_identity(&self) -> &ComputationProductId {
782        self.matrix.product_identity()
783    }
784    pub const fn owner(&self) -> OwnerId {
785        self.matrix.owner()
786    }
787
788    pub const fn consumer_id(&self) -> ConsumerId {
789        self.matrix.consumer_id()
790    }
791
792    pub const fn precision(&self) -> AbsoluteBits {
793        self.matrix.precision()
794    }
795
796    pub const fn source(&self) -> NecoImplementationSource {
797        self.matrix.source()
798    }
799
800    pub fn absolute_error_bound(&self) -> &Dyadic {
801        self.matrix.absolute_error_bound()
802    }
803}
804
805pub trait IntoMassNormalizationReference {
806    fn into_mass_normalization_reference(self) -> Option<MassNormalizationReference>;
807}
808
809impl IntoMassNormalizationReference for MassNormalizationReference {
810    fn into_mass_normalization_reference(self) -> Option<MassNormalizationReference> {
811        Some(self)
812    }
813}
814
815impl IntoMassNormalizationReference for Option<MassNormalizationReference> {
816    fn into_mass_normalization_reference(self) -> Option<MassNormalizationReference> {
817        self
818    }
819}
820
821#[derive(Debug, PartialEq)]
822pub struct CertifiedGeneralizedEigenInput {
823    stiffness: CertifiedMatrixInput,
824    mass: MassNormalizationReference,
825}
826
827impl CertifiedGeneralizedEigenInput {
828    pub fn new<M>(stiffness: CertifiedMatrixInput, mass: M) -> Result<Self, NecoFailure>
829    where
830        M: IntoMassNormalizationReference,
831    {
832        let mass =
833            mass.into_mass_normalization_reference()
834                .ok_or(NecoFailure::MissingMatrixInput {
835                    location: matrix_location(
836                        MatrixInputRole::MassNormalization,
837                        stiffness.consumer_id(),
838                        None,
839                    ),
840                })?;
841        let stiffness_shape = stiffness.shape();
842        let mass_shape = mass.matrix().shape();
843        if stiffness_shape != mass_shape {
844            return Err(matrix_mismatch(
845                matrix_location(
846                    MatrixInputRole::MassNormalization,
847                    mass.matrix().consumer_id(),
848                    None,
849                ),
850                MatrixInputMismatchField::Shape,
851                matrix_provenance(
852                    stiffness.owner(),
853                    stiffness.consumer_id(),
854                    stiffness.precision(),
855                    stiffness.source(),
856                    stiffness.product_identity(),
857                ),
858                matrix_provenance(
859                    mass.matrix().owner(),
860                    mass.matrix().consumer_id(),
861                    mass.matrix().precision(),
862                    mass.matrix().source(),
863                    mass.product_identity(),
864                ),
865            ));
866        }
867        let expected = matrix_provenance(
868            stiffness.owner(),
869            stiffness.consumer_id(),
870            stiffness.precision(),
871            stiffness.source(),
872            stiffness.product_identity(),
873        );
874        let actual = matrix_provenance(
875            mass.matrix().owner(),
876            mass.matrix().consumer_id(),
877            mass.matrix().precision(),
878            mass.matrix().source(),
879            mass.product_identity(),
880        );
881        if let Some(field) = generalized_provenance_mismatch_field(&expected, &actual) {
882            return Err(NecoFailure::ProvenanceMismatch {
883                location: matrix_location(
884                    MatrixInputRole::MassNormalization,
885                    mass.matrix().consumer_id(),
886                    None,
887                ),
888                payload: Box::new(ProvenanceMismatchPayload::new(field, expected, actual)),
889            });
890        }
891        Ok(Self { stiffness, mass })
892    }
893
894    pub fn stiffness(&self) -> &CertifiedMatrixInput {
895        &self.stiffness
896    }
897
898    pub fn mass(&self) -> &MassNormalizationReference {
899        &self.mass
900    }
901
902    pub fn product_identity(&self) -> &ComputationProductId {
903        self.stiffness.product_identity()
904    }
905}
906
907fn row_column(shape: Shape, index: usize) -> (usize, usize) {
908    (index / shape.columns(), index % shape.columns())
909}
910
911fn matrix_location(
912    role: MatrixInputRole,
913    consumer: ConsumerId,
914    coordinates: Option<(usize, usize)>,
915) -> FailureLocation {
916    let location = FailureLocation::operation(FailureOperation::Assemble)
917        .with_matrix_role(role)
918        .with_consumer(consumer);
919    match coordinates {
920        Some((row, column)) => location.with_matrix_location(row, column),
921        None => location,
922    }
923}
924
925fn matrix_provenance(
926    owner: OwnerId,
927    consumer: ConsumerId,
928    precision: AbsoluteBits,
929    source: NecoImplementationSource,
930    product_identity: &ComputationProductId,
931) -> ProvenanceRecord {
932    ProvenanceRecord::new(
933        Some(owner),
934        Some(consumer),
935        None,
936        Some(precision),
937        Some(source.revision_identity()),
938        Some(source.public_api_identity()),
939    )
940    .with_product_identity(product_identity.clone())
941}
942
943fn provenance_mismatch_field(
944    expected: &ProvenanceRecord,
945    actual: &ProvenanceRecord,
946) -> Option<ProvenanceMismatchField> {
947    if expected.consumer_id() != actual.consumer_id() {
948        Some(ProvenanceMismatchField::Consumer)
949    } else if expected.owner() != actual.owner() {
950        Some(ProvenanceMismatchField::Owner)
951    } else if expected.expr_id() != actual.expr_id() {
952        Some(ProvenanceMismatchField::Expression)
953    } else if expected.precision() != actual.precision() {
954        Some(ProvenanceMismatchField::Precision)
955    } else if expected.revision_identity() != actual.revision_identity()
956        || expected.public_api_identity() != actual.public_api_identity()
957    {
958        Some(ProvenanceMismatchField::Source)
959    } else if expected.product_identity() != actual.product_identity() {
960        Some(ProvenanceMismatchField::Product)
961    } else {
962        None
963    }
964}
965fn generalized_provenance_mismatch_field(
966    expected: &ProvenanceRecord,
967    actual: &ProvenanceRecord,
968) -> Option<ProvenanceMismatchField> {
969    if expected.owner() != actual.owner() {
970        Some(ProvenanceMismatchField::Owner)
971    } else if expected.precision() != actual.precision() {
972        Some(ProvenanceMismatchField::Precision)
973    } else if expected.revision_identity() != actual.revision_identity()
974        || expected.public_api_identity() != actual.public_api_identity()
975    {
976        Some(ProvenanceMismatchField::Source)
977    } else if expected.product_identity() != actual.product_identity() {
978        Some(ProvenanceMismatchField::Product)
979    } else {
980        None
981    }
982}
983
984fn matrix_payload(
985    location: &FailureLocation,
986    field: MatrixInputMismatchField,
987    expected: ProvenanceRecord,
988    actual: ProvenanceRecord,
989) -> MatrixInputMismatchPayload {
990    let mut payload = MatrixInputMismatchPayload::new(field, expected.clone(), actual.clone())
991        .with_products(expected.product_identity(), actual.product_identity());
992    if let (Some(row), Some(column)) = (location.row(), location.column()) {
993        payload = payload.with_location(row, column);
994    }
995    payload
996}
997
998fn matrix_mismatch(
999    location: FailureLocation,
1000    field: MatrixInputMismatchField,
1001    expected: ProvenanceRecord,
1002    actual: ProvenanceRecord,
1003) -> NecoFailure {
1004    NecoFailure::MatrixInputMismatch {
1005        payload: Box::new(matrix_payload(&location, field, expected, actual)),
1006        location,
1007    }
1008}
1009
1010#[derive(Default)]
1011struct MismatchDetails {
1012    expected_expr: Option<ExprId>,
1013    actual_expr: Option<ExprId>,
1014    expected_bits: Option<u64>,
1015    actual_bits: Option<u64>,
1016}
1017
1018fn matrix_mismatch_with_details(
1019    location: FailureLocation,
1020    field: MatrixInputMismatchField,
1021    expected: ProvenanceRecord,
1022    actual: ProvenanceRecord,
1023    details: MismatchDetails,
1024) -> NecoFailure {
1025    NecoFailure::MatrixInputMismatch {
1026        payload: Box::new(
1027            matrix_payload(&location, field, expected, actual)
1028                .with_expressions(details.expected_expr, details.actual_expr)
1029                .with_value_bits(details.expected_bits, details.actual_bits),
1030        ),
1031        location,
1032    }
1033}
1034
1035fn storage_failure(role: MatrixInputRole, consumer: ConsumerId, error: BigintError) -> NecoFailure {
1036    NecoFailure::StorageFailure {
1037        location: matrix_location(role, consumer, None),
1038        payload: Box::new(StorageFailurePayload::Bigint(error)),
1039    }
1040}
1041
1042pub fn project_vector_f64<T: CertifiedF64Scalar>(
1043    vector: &Vector<T>,
1044    policy: ProjectionPolicy,
1045) -> Result<CertifiedVectorProjection, CertifiedLinearProjectionError> {
1046    let mut values = Vec::new();
1047    let mut certificates = Vec::new();
1048    values
1049        .try_reserve_exact(vector.len())
1050        .map_err(|_| LinearError::AllocationFailure {
1051            requested: vector.len(),
1052        })?;
1053    certificates
1054        .try_reserve_exact(vector.len())
1055        .map_err(|_| LinearError::AllocationFailure {
1056            requested: vector.len(),
1057        })?;
1058    let mut absolute_error_bound = Dyadic::from_f64_exact(0.0)?;
1059    for (index, value) in vector.values().iter().enumerate() {
1060        let certificate = value
1061            .project_f64_scalar(policy)
1062            .map_err(|source| CertifiedLinearProjectionError::VectorElement { index, source })?;
1063        absolute_error_bound = absolute_error_bound.add(certificate.absolute_error())?;
1064        values.push(certificate.value());
1065        certificates.push(certificate);
1066    }
1067    Ok(CertifiedVectorProjection {
1068        policy,
1069        values: Vector::try_from_vec(values)?,
1070        certificates,
1071        absolute_error_bound,
1072    })
1073}
1074
1075pub fn project_matrix_f64<T: CertifiedF64Scalar>(
1076    matrix: &ExactMatrix<T>,
1077    policy: ProjectionPolicy,
1078) -> Result<CertifiedMatrixProjection, CertifiedLinearProjectionError> {
1079    let element_count = matrix.shape().element_count()?;
1080    let mut values = Vec::new();
1081    let mut certificates_row_major = Vec::new();
1082    values
1083        .try_reserve_exact(element_count)
1084        .map_err(|_| LinearError::AllocationFailure {
1085            requested: element_count,
1086        })?;
1087    certificates_row_major
1088        .try_reserve_exact(element_count)
1089        .map_err(|_| LinearError::AllocationFailure {
1090            requested: element_count,
1091        })?;
1092    let mut absolute_error_bound = Dyadic::from_f64_exact(0.0)?;
1093    for (index, value) in matrix.values().iter().enumerate() {
1094        let row = index / matrix.columns();
1095        let column = index % matrix.columns();
1096        let certificate = value.project_f64_scalar(policy).map_err(|source| {
1097            CertifiedLinearProjectionError::MatrixElement {
1098                row,
1099                column,
1100                source,
1101            }
1102        })?;
1103        absolute_error_bound = absolute_error_bound.add(certificate.absolute_error())?;
1104        values.push(certificate.value());
1105        certificates_row_major.push(certificate);
1106    }
1107    Ok(CertifiedMatrixProjection {
1108        policy,
1109        matrix: DenseMatrix::from_row_major(matrix.shape(), values)?,
1110        certificates_row_major,
1111        absolute_error_bound,
1112    })
1113}
1114
1115pub trait ExactScalar: Sized {
1116    fn try_clone(&self) -> Result<Self, ExactLinearError>;
1117
1118    fn zero() -> Result<Self, ExactLinearError>;
1119
1120    fn one() -> Result<Self, ExactLinearError>;
1121
1122    fn is_zero(&self) -> bool;
1123
1124    fn add(&self, rhs: &Self) -> Result<Self, ExactLinearError>;
1125
1126    fn sub(&self, rhs: &Self) -> Result<Self, ExactLinearError>;
1127
1128    fn mul(&self, rhs: &Self) -> Result<Self, ExactLinearError>;
1129
1130    fn div(&self, rhs: &Self) -> Result<Self, ExactLinearError>;
1131}
1132
1133impl ExactScalar for ReducedRational {
1134    fn try_clone(&self) -> Result<Self, ExactLinearError> {
1135        Ok(self.try_clone()?)
1136    }
1137
1138    fn zero() -> Result<Self, ExactLinearError> {
1139        Ok(Self::from_bigint(BigInt::zero())?)
1140    }
1141
1142    fn one() -> Result<Self, ExactLinearError> {
1143        Ok(Self::from_bigint(BigInt::one()?)?)
1144    }
1145
1146    fn is_zero(&self) -> bool {
1147        self.is_zero()
1148    }
1149
1150    fn add(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1151        Ok(self.add(rhs)?)
1152    }
1153
1154    fn sub(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1155        Ok(self.sub(rhs)?)
1156    }
1157
1158    fn mul(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1159        Ok(self.mul(rhs)?)
1160    }
1161
1162    fn div(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1163        Ok(self.div(rhs)?)
1164    }
1165}
1166
1167impl ExactScalar for FormSum {
1168    fn try_clone(&self) -> Result<Self, ExactLinearError> {
1169        Ok(self.try_clone()?)
1170    }
1171
1172    fn zero() -> Result<Self, ExactLinearError> {
1173        Ok(Self::zero())
1174    }
1175
1176    fn one() -> Result<Self, ExactLinearError> {
1177        Ok(Self::one()?)
1178    }
1179
1180    fn is_zero(&self) -> bool {
1181        self.is_zero()
1182    }
1183
1184    fn add(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1185        Ok(self.add(rhs)?)
1186    }
1187
1188    fn sub(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1189        Ok(self.sub(rhs)?)
1190    }
1191
1192    fn mul(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1193        Ok(self.mul(rhs)?)
1194    }
1195
1196    fn div(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1197        Ok(self.div(rhs)?)
1198    }
1199}
1200
1201impl ExactScalar for RealAlgebraic {
1202    fn try_clone(&self) -> Result<Self, ExactLinearError> {
1203        Ok(self.try_clone()?)
1204    }
1205
1206    fn zero() -> Result<Self, ExactLinearError> {
1207        Ok(Self::from_form_sum(&FormSum::zero())?)
1208    }
1209
1210    fn one() -> Result<Self, ExactLinearError> {
1211        Ok(Self::from_form_sum(&FormSum::one()?)?)
1212    }
1213
1214    fn is_zero(&self) -> bool {
1215        self.is_zero()
1216    }
1217
1218    fn add(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1219        Ok(self.add(rhs)?)
1220    }
1221
1222    fn sub(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1223        Ok(self.sub(rhs)?)
1224    }
1225
1226    fn mul(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1227        Ok(self.mul(rhs)?)
1228    }
1229
1230    fn div(&self, rhs: &Self) -> Result<Self, ExactLinearError> {
1231        Ok(self.div(rhs)?)
1232    }
1233}
1234
1235#[derive(Debug, Eq, PartialEq)]
1236pub struct ExactMatrix<T> {
1237    shape: Shape,
1238    values: Vec<T>,
1239}
1240
1241impl<T> ExactMatrix<T> {
1242    pub fn from_row_major(shape: Shape, values: Vec<T>) -> Result<Self, ExactLinearError> {
1243        let expected = shape.element_count()?;
1244        if values.len() != expected {
1245            return Err(LinearError::StorageLengthMismatch {
1246                expected,
1247                actual: values.len(),
1248            }
1249            .into());
1250        }
1251        if values.len() > isize::MAX as usize {
1252            return Err(LinearError::InvalidStorage {
1253                reason: "matrix length exceeds the representable allocation limit",
1254            }
1255            .into());
1256        }
1257        Ok(Self { shape, values })
1258    }
1259
1260    pub fn shape(&self) -> Shape {
1261        self.shape
1262    }
1263
1264    pub fn rows(&self) -> usize {
1265        self.shape.rows()
1266    }
1267
1268    pub fn columns(&self) -> usize {
1269        self.shape.columns()
1270    }
1271
1272    pub fn value(&self, row: RowIndex, column: ColumnIndex) -> Result<&T, ExactLinearError> {
1273        let position = self.position(row, column)?;
1274        self.values.get(position).ok_or_else(|| {
1275            LinearError::InvalidStorage {
1276                reason: "matrix storage is shorter than its declared shape",
1277            }
1278            .into()
1279        })
1280    }
1281
1282    pub fn values(&self) -> &[T] {
1283        &self.values
1284    }
1285
1286    fn position(&self, row: RowIndex, column: ColumnIndex) -> Result<usize, ExactLinearError> {
1287        if row.value() >= self.rows() {
1288            return Err(LinearError::IndexOutOfBounds {
1289                axis: "row",
1290                index: row.value(),
1291                bound: self.rows(),
1292            }
1293            .into());
1294        }
1295        if column.value() >= self.columns() {
1296            return Err(LinearError::IndexOutOfBounds {
1297                axis: "column",
1298                index: column.value(),
1299                bound: self.columns(),
1300            }
1301            .into());
1302        }
1303        row.value()
1304            .checked_mul(self.columns())
1305            .and_then(|offset| offset.checked_add(column.value()))
1306            .ok_or(LinearError::CapacityOverflow {
1307                requested: usize::MAX,
1308            })
1309            .map_err(Into::into)
1310    }
1311}
1312
1313#[derive(Debug, Eq, PartialEq)]
1314pub enum ExactLinearSolution<T> {
1315    Unique(Vector<T>),
1316    Affine {
1317        particular: Vector<T>,
1318        kernel: Vec<Vector<T>>,
1319    },
1320    Inconsistent,
1321}
1322
1323impl<T> ExactMatrix<T>
1324where
1325    T: ExactScalar,
1326{
1327    pub fn determinant(&self) -> Result<T, ExactLinearError> {
1328        if self.rows() != self.columns() {
1329            return Err(ExactLinearError::NonSquareMatrix {
1330                rows: self.rows(),
1331                columns: self.columns(),
1332            });
1333        }
1334        let elimination = self.eliminate(None)?;
1335        if elimination.pivots.len() != self.rows() {
1336            return T::zero();
1337        }
1338        let mut determinant = if elimination.swap_count & 1 == 0 {
1339            T::one()?
1340        } else {
1341            T::zero()?.sub(&T::one()?)?
1342        };
1343        for pivot in elimination.pivot_values {
1344            determinant = determinant.mul(&pivot)?;
1345        }
1346        Ok(determinant)
1347    }
1348
1349    pub fn rank(&self) -> Result<usize, ExactLinearError> {
1350        Ok(self.eliminate(None)?.pivots.len())
1351    }
1352
1353    pub fn kernel_basis(&self) -> Result<Vec<Vector<T>>, ExactLinearError> {
1354        let elimination = self.eliminate(None)?;
1355        kernel_basis(&elimination, self.columns())
1356    }
1357
1358    pub fn solve(&self, rhs: &Vector<T>) -> Result<ExactLinearSolution<T>, ExactLinearError> {
1359        if rhs.len() != self.rows() {
1360            return Err(LinearError::StorageLengthMismatch {
1361                expected: self.rows(),
1362                actual: rhs.len(),
1363            }
1364            .into());
1365        }
1366        let elimination = self.eliminate(Some(rhs))?;
1367        if elimination.inconsistent {
1368            return Ok(ExactLinearSolution::Inconsistent);
1369        }
1370        let particular = solution_vector(&elimination, self.columns())?;
1371        if elimination.pivots.len() == self.columns() {
1372            return Ok(ExactLinearSolution::Unique(particular));
1373        }
1374        Ok(ExactLinearSolution::Affine {
1375            particular,
1376            kernel: kernel_basis(&elimination, self.columns())?,
1377        })
1378    }
1379
1380    /// Scans columns from left to right and selects the first nonzero row at or
1381    /// below the pivot row.
1382    fn eliminate(&self, rhs: Option<&Vector<T>>) -> Result<Elimination<T>, ExactLinearError> {
1383        let rows = self.rows();
1384        let columns = self.columns();
1385        let element_count = self.shape.element_count()?;
1386        let mut coefficients = try_clone_values(&self.values, element_count)?;
1387        let mut right_hand_side = match rhs {
1388            Some(rhs) => Some(try_clone_values(rhs.values(), rows)?),
1389            None => None,
1390        };
1391        let mut pivots = try_vec_capacity(columns)?;
1392        let mut pivot_values = try_vec_capacity(columns)?;
1393        let mut pivot_row = 0_usize;
1394        let mut swap_count = 0_usize;
1395
1396        for pivot_column in 0..columns {
1397            let mut selected = None;
1398            for row in pivot_row..rows {
1399                if !coefficient(&coefficients, columns, row, pivot_column)?.is_zero() {
1400                    selected = Some(row);
1401                    break;
1402                }
1403            }
1404            let Some(selected_row) = selected else {
1405                continue;
1406            };
1407            if selected_row != pivot_row {
1408                swap_rows(&mut coefficients, columns, selected_row, pivot_row)?;
1409                if let Some(values) = right_hand_side.as_mut() {
1410                    values.swap(selected_row, pivot_row);
1411                }
1412                swap_count = swap_count
1413                    .checked_add(1)
1414                    .ok_or(LinearError::CapacityOverflow {
1415                        requested: usize::MAX,
1416                    })?;
1417            }
1418
1419            let pivot =
1420                coefficient(&coefficients, columns, pivot_row, pivot_column)?.try_clone()?;
1421            pivot_values.push(pivot.try_clone()?);
1422            normalize_row(
1423                &mut coefficients,
1424                right_hand_side.as_mut(),
1425                columns,
1426                pivot_row,
1427                pivot_column,
1428                &pivot,
1429            )?;
1430            for row in 0..rows {
1431                if row == pivot_row {
1432                    continue;
1433                }
1434                eliminate_row(
1435                    &mut coefficients,
1436                    right_hand_side.as_mut(),
1437                    columns,
1438                    row,
1439                    pivot_row,
1440                    pivot_column,
1441                )?;
1442            }
1443            pivots.push(pivot_column);
1444            pivot_row = pivot_row
1445                .checked_add(1)
1446                .ok_or(LinearError::CapacityOverflow {
1447                    requested: usize::MAX,
1448                })?;
1449            if pivot_row == rows {
1450                break;
1451            }
1452        }
1453
1454        let inconsistent = match right_hand_side.as_ref() {
1455            Some(values) => has_inconsistent_row(&coefficients, values, rows, columns)?,
1456            None => false,
1457        };
1458        Ok(Elimination {
1459            coefficients,
1460            right_hand_side,
1461            pivots,
1462            pivot_values,
1463            swap_count,
1464            inconsistent,
1465        })
1466    }
1467}
1468
1469struct Elimination<T> {
1470    coefficients: Vec<T>,
1471    right_hand_side: Option<Vec<T>>,
1472    pivots: Vec<usize>,
1473    pivot_values: Vec<T>,
1474    swap_count: usize,
1475    inconsistent: bool,
1476}
1477
1478fn try_vec_capacity<T>(requested: usize) -> Result<Vec<T>, ExactLinearError> {
1479    #[cfg(test)]
1480    if INJECT_NEXT_ALLOCATION_FAILURE.with(|failure| failure.replace(false)) {
1481        return Err(LinearError::AllocationFailure { requested }.into());
1482    }
1483
1484    let mut values = Vec::new();
1485    values
1486        .try_reserve_exact(requested)
1487        .map_err(|_| LinearError::AllocationFailure { requested })?;
1488    Ok(values)
1489}
1490
1491fn try_clone_values<T: ExactScalar>(
1492    values: &[T],
1493    requested: usize,
1494) -> Result<Vec<T>, ExactLinearError> {
1495    let mut copied = try_vec_capacity(requested)?;
1496    for value in values {
1497        copied.push(value.try_clone()?);
1498    }
1499    Ok(copied)
1500}
1501
1502fn coefficient<T>(
1503    coefficients: &[T],
1504    columns: usize,
1505    row: usize,
1506    column: usize,
1507) -> Result<&T, ExactLinearError> {
1508    let position = row
1509        .checked_mul(columns)
1510        .and_then(|offset| offset.checked_add(column))
1511        .ok_or(LinearError::CapacityOverflow {
1512            requested: usize::MAX,
1513        })?;
1514    coefficients.get(position).ok_or_else(|| {
1515        LinearError::InvalidStorage {
1516            reason: "elimination storage is shorter than its declared shape",
1517        }
1518        .into()
1519    })
1520}
1521
1522fn coefficient_mut<T>(
1523    coefficients: &mut [T],
1524    columns: usize,
1525    row: usize,
1526    column: usize,
1527) -> Result<&mut T, ExactLinearError> {
1528    let position = row
1529        .checked_mul(columns)
1530        .and_then(|offset| offset.checked_add(column))
1531        .ok_or(LinearError::CapacityOverflow {
1532            requested: usize::MAX,
1533        })?;
1534    coefficients.get_mut(position).ok_or_else(|| {
1535        LinearError::InvalidStorage {
1536            reason: "elimination storage is shorter than its declared shape",
1537        }
1538        .into()
1539    })
1540}
1541
1542fn swap_rows<T>(
1543    coefficients: &mut [T],
1544    columns: usize,
1545    first: usize,
1546    second: usize,
1547) -> Result<(), ExactLinearError> {
1548    for column in 0..columns {
1549        let first_position = first
1550            .checked_mul(columns)
1551            .and_then(|offset| offset.checked_add(column))
1552            .ok_or(LinearError::CapacityOverflow {
1553                requested: usize::MAX,
1554            })?;
1555        let second_position = second
1556            .checked_mul(columns)
1557            .and_then(|offset| offset.checked_add(column))
1558            .ok_or(LinearError::CapacityOverflow {
1559                requested: usize::MAX,
1560            })?;
1561        if first_position >= coefficients.len() || second_position >= coefficients.len() {
1562            return Err(LinearError::InvalidStorage {
1563                reason: "elimination storage is shorter than its declared shape",
1564            }
1565            .into());
1566        }
1567        coefficients.swap(first_position, second_position);
1568    }
1569    Ok(())
1570}
1571
1572fn normalize_row<T: ExactScalar>(
1573    coefficients: &mut [T],
1574    right_hand_side: Option<&mut Vec<T>>,
1575    columns: usize,
1576    row: usize,
1577    pivot_column: usize,
1578    pivot: &T,
1579) -> Result<(), ExactLinearError> {
1580    for column in pivot_column..columns {
1581        let normalized = coefficient(coefficients, columns, row, column)?.div(pivot)?;
1582        *coefficient_mut(coefficients, columns, row, column)? = normalized;
1583    }
1584    if let Some(values) = right_hand_side {
1585        let value = values.get(row).ok_or(LinearError::InvalidStorage {
1586            reason: "right-hand-side storage is shorter than its declared shape",
1587        })?;
1588        let normalized = value.div(pivot)?;
1589        *values.get_mut(row).ok_or(LinearError::InvalidStorage {
1590            reason: "right-hand-side storage is shorter than its declared shape",
1591        })? = normalized;
1592    }
1593    Ok(())
1594}
1595
1596fn eliminate_row<T: ExactScalar>(
1597    coefficients: &mut [T],
1598    right_hand_side: Option<&mut Vec<T>>,
1599    columns: usize,
1600    target_row: usize,
1601    pivot_row: usize,
1602    pivot_column: usize,
1603) -> Result<(), ExactLinearError> {
1604    let factor = coefficient(coefficients, columns, target_row, pivot_column)?.try_clone()?;
1605    if factor.is_zero() {
1606        return Ok(());
1607    }
1608    for column in pivot_column..columns {
1609        let pivot_value = coefficient(coefficients, columns, pivot_row, column)?.try_clone()?;
1610        let target_value = coefficient(coefficients, columns, target_row, column)?.try_clone()?;
1611        let value = target_value.sub(&factor.mul(&pivot_value)?)?;
1612        *coefficient_mut(coefficients, columns, target_row, column)? = value;
1613    }
1614    if let Some(values) = right_hand_side {
1615        let pivot_value = values
1616            .get(pivot_row)
1617            .ok_or(LinearError::InvalidStorage {
1618                reason: "right-hand-side storage is shorter than its declared shape",
1619            })?
1620            .try_clone()?;
1621        let target_value = values
1622            .get(target_row)
1623            .ok_or(LinearError::InvalidStorage {
1624                reason: "right-hand-side storage is shorter than its declared shape",
1625            })?
1626            .try_clone()?;
1627        let value = target_value.sub(&factor.mul(&pivot_value)?)?;
1628        *values
1629            .get_mut(target_row)
1630            .ok_or(LinearError::InvalidStorage {
1631                reason: "right-hand-side storage is shorter than its declared shape",
1632            })? = value;
1633    }
1634    Ok(())
1635}
1636
1637fn has_inconsistent_row<T: ExactScalar>(
1638    coefficients: &[T],
1639    right_hand_side: &[T],
1640    rows: usize,
1641    columns: usize,
1642) -> Result<bool, ExactLinearError> {
1643    if right_hand_side.len() != rows {
1644        return Err(LinearError::StorageLengthMismatch {
1645            expected: rows,
1646            actual: right_hand_side.len(),
1647        }
1648        .into());
1649    }
1650    for (row, value) in right_hand_side.iter().enumerate() {
1651        let mut all_zero = true;
1652        for column in 0..columns {
1653            if !coefficient(coefficients, columns, row, column)?.is_zero() {
1654                all_zero = false;
1655                break;
1656            }
1657        }
1658        if all_zero && !value.is_zero() {
1659            return Ok(true);
1660        }
1661    }
1662    Ok(false)
1663}
1664
1665fn solution_vector<T: ExactScalar>(
1666    elimination: &Elimination<T>,
1667    columns: usize,
1668) -> Result<Vector<T>, ExactLinearError> {
1669    let right_hand_side =
1670        elimination
1671            .right_hand_side
1672            .as_ref()
1673            .ok_or(LinearError::InvalidStorage {
1674                reason: "solution requires a right-hand-side vector",
1675            })?;
1676    let mut values = try_vec_capacity(columns)?;
1677    for _ in 0..columns {
1678        values.push(T::zero()?);
1679    }
1680    for (row, column) in elimination.pivots.iter().copied().enumerate() {
1681        let value = right_hand_side
1682            .get(row)
1683            .ok_or(LinearError::InvalidStorage {
1684                reason: "right-hand-side storage is shorter than pivot rows",
1685            })?
1686            .try_clone()?;
1687        *values.get_mut(column).ok_or(LinearError::InvalidStorage {
1688            reason: "solution storage is shorter than its declared dimension",
1689        })? = value;
1690    }
1691    Ok(Vector::try_from_vec(values)?)
1692}
1693
1694fn kernel_basis<T: ExactScalar>(
1695    elimination: &Elimination<T>,
1696    columns: usize,
1697) -> Result<Vec<Vector<T>>, ExactLinearError> {
1698    let mut is_pivot = try_vec_capacity(columns)?;
1699    is_pivot.resize(columns, false);
1700    for column in &elimination.pivots {
1701        *is_pivot
1702            .get_mut(*column)
1703            .ok_or(LinearError::InvalidStorage {
1704                reason: "pivot column exceeds matrix dimension",
1705            })? = true;
1706    }
1707    let free_count =
1708        columns
1709            .checked_sub(elimination.pivots.len())
1710            .ok_or(LinearError::InvalidStorage {
1711                reason: "pivot count exceeds matrix dimension",
1712            })?;
1713    let mut basis = try_vec_capacity(free_count)?;
1714    for (free_column, pivoted) in is_pivot.iter().copied().enumerate() {
1715        if pivoted {
1716            continue;
1717        }
1718        let mut values = try_vec_capacity(columns)?;
1719        for column in 0..columns {
1720            values.push(if column == free_column {
1721                T::one()?
1722            } else {
1723                T::zero()?
1724            });
1725        }
1726        for (row, pivot_column) in elimination.pivots.iter().copied().enumerate() {
1727            let factor = coefficient(&elimination.coefficients, columns, row, free_column)?;
1728            let negated = T::zero()?.sub(factor)?;
1729            *values
1730                .get_mut(pivot_column)
1731                .ok_or(LinearError::InvalidStorage {
1732                    reason: "kernel vector storage is shorter than matrix dimension",
1733                })? = negated;
1734        }
1735        basis.push(Vector::try_from_vec(values)?);
1736    }
1737    Ok(basis)
1738}
1739
1740#[cfg(test)]
1741mod tests {
1742    use alloc::vec;
1743
1744    use super::{
1745        project_matrix_f64, project_vector_f64, CertifiedF64Scalar, CertifiedLinearProjectionError,
1746        ExactLinearSolution, ExactMatrix, ExactScalar,
1747    };
1748    use neco_algnum::RealAlgebraic;
1749    use neco_bigint::{BigInt, Dyadic, ReducedRational};
1750    use neco_expr::{AbsoluteBits, ProjectionPolicy, ScalarProjectionError};
1751    use neco_formsum::FormSum;
1752    use neco_linear_types::{Shape, Vector};
1753
1754    fn integer(value: i32) -> ReducedRational {
1755        ReducedRational::from_bigint(BigInt::try_from(value).expect("small integer"))
1756            .expect("valid rational")
1757    }
1758
1759    fn vector(values: &[i32]) -> Vector<ReducedRational> {
1760        Vector::try_from_vec(values.iter().copied().map(integer).collect()).expect("valid vector")
1761    }
1762
1763    fn matrix(rows: usize, columns: usize, values: &[i32]) -> ExactMatrix<ReducedRational> {
1764        ExactMatrix::from_row_major(
1765            Shape::new(rows, columns),
1766            values.iter().copied().map(integer).collect(),
1767        )
1768        .expect("valid matrix")
1769    }
1770
1771    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
1772    enum FailureStage {
1773        Clone,
1774        Divide,
1775        Multiply,
1776    }
1777
1778    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
1779    struct FailingScalar {
1780        value: i32,
1781        failure_stage: FailureStage,
1782    }
1783
1784    impl FailingScalar {
1785        fn new(value: i32, failure_stage: FailureStage) -> Self {
1786            Self {
1787                value,
1788                failure_stage,
1789            }
1790        }
1791
1792        fn failure(reason: &'static str) -> super::ExactLinearError {
1793            super::ExactLinearError::Linear(neco_linear_types::LinearError::InvalidStorage {
1794                reason,
1795            })
1796        }
1797    }
1798
1799    impl ExactScalar for FailingScalar {
1800        fn try_clone(&self) -> Result<Self, super::ExactLinearError> {
1801            if self.failure_stage == FailureStage::Clone {
1802                return Err(Self::failure("test exact scalar clone failure"));
1803            }
1804            Ok(*self)
1805        }
1806
1807        fn zero() -> Result<Self, super::ExactLinearError> {
1808            Ok(Self::new(0, FailureStage::Divide))
1809        }
1810
1811        fn one() -> Result<Self, super::ExactLinearError> {
1812            Ok(Self::new(1, FailureStage::Divide))
1813        }
1814
1815        fn is_zero(&self) -> bool {
1816            self.value == 0
1817        }
1818
1819        fn add(&self, rhs: &Self) -> Result<Self, super::ExactLinearError> {
1820            Ok(Self::new(self.value + rhs.value, self.failure_stage))
1821        }
1822
1823        fn sub(&self, rhs: &Self) -> Result<Self, super::ExactLinearError> {
1824            Ok(Self::new(self.value - rhs.value, self.failure_stage))
1825        }
1826
1827        fn mul(&self, rhs: &Self) -> Result<Self, super::ExactLinearError> {
1828            if self.failure_stage == FailureStage::Multiply {
1829                return Err(Self::failure("test exact scalar multiplication failure"));
1830            }
1831            Ok(Self::new(self.value * rhs.value, self.failure_stage))
1832        }
1833
1834        fn div(&self, rhs: &Self) -> Result<Self, super::ExactLinearError> {
1835            if self.failure_stage == FailureStage::Divide {
1836                return Err(Self::failure("test exact scalar division failure"));
1837            }
1838            Ok(Self::new(self.value / rhs.value, self.failure_stage))
1839        }
1840    }
1841
1842    fn failing_matrix(
1843        rows: usize,
1844        columns: usize,
1845        values: &[i32],
1846        failure_stage: FailureStage,
1847    ) -> ExactMatrix<FailingScalar> {
1848        ExactMatrix::from_row_major(
1849            Shape::new(rows, columns),
1850            values
1851                .iter()
1852                .copied()
1853                .map(|value| FailingScalar::new(value, failure_stage))
1854                .collect(),
1855        )
1856        .expect("valid matrix")
1857    }
1858
1859    fn failing_vector(values: &[i32], failure_stage: FailureStage) -> Vector<FailingScalar> {
1860        Vector::try_from_vec(
1861            values
1862                .iter()
1863                .copied()
1864                .map(|value| FailingScalar::new(value, failure_stage))
1865                .collect(),
1866        )
1867        .expect("valid vector")
1868    }
1869
1870    impl CertifiedF64Scalar for FailingScalar {
1871        fn project_f64_scalar(
1872            &self,
1873            _policy: ProjectionPolicy,
1874        ) -> Result<neco_expr::CertifiedScalarProjection, ScalarProjectionError> {
1875            Err(ScalarProjectionError::FloatOutOfRange)
1876        }
1877    }
1878
1879    fn error_sum(certificates: &[neco_expr::CertifiedScalarProjection]) -> Dyadic {
1880        certificates
1881            .iter()
1882            .try_fold(
1883                Dyadic::from_f64_exact(0.0).expect("zero dyadic"),
1884                |sum, certificate| sum.add(certificate.absolute_error()),
1885            )
1886            .expect("error sum")
1887    }
1888
1889    #[test]
1890    fn certified_vector_projection_keeps_each_certificate_and_total_error() {
1891        let policy = ProjectionPolicy::new(AbsoluteBits::new(20));
1892        let projection = project_vector_f64(&vector(&[1, -2]), policy).expect("projection");
1893
1894        assert_eq!(projection.policy(), policy);
1895        assert_eq!(projection.values().values(), &[1.0, -2.0]);
1896        assert_eq!(projection.certificates().len(), 2);
1897        assert_eq!(
1898            projection
1899                .certificates()
1900                .iter()
1901                .map(neco_expr::CertifiedScalarProjection::value)
1902                .collect::<Vec<_>>(),
1903            projection.values().values()
1904        );
1905        assert_eq!(
1906            projection.absolute_error_bound(),
1907            &error_sum(projection.certificates())
1908        );
1909    }
1910
1911    #[test]
1912    fn certified_matrix_projection_uses_logical_row_major_certificates() {
1913        let policy = ProjectionPolicy::new(AbsoluteBits::new(20));
1914        let projection =
1915            project_matrix_f64(&matrix(2, 2, &[1, 2, 3, 4]), policy).expect("projection");
1916
1917        assert_eq!(projection.policy(), policy);
1918        assert_eq!(projection.matrix().shape(), Shape::new(2, 2));
1919        assert_eq!(projection.certificates_row_major().len(), 4);
1920        for (row, column, expected) in [(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)] {
1921            let shape = Shape::new(2, 2);
1922            let row = shape.row_index(row).expect("row index");
1923            let column = shape.column_index(column).expect("column index");
1924            assert_eq!(projection.matrix().value(row, column), Ok(&expected));
1925            assert_eq!(
1926                projection.certificate(row, column).unwrap().value(),
1927                expected
1928            );
1929        }
1930        assert_eq!(
1931            projection.absolute_error_bound(),
1932            &error_sum(projection.certificates_row_major())
1933        );
1934    }
1935
1936    #[test]
1937    fn certified_matrix_projection_reports_the_failing_logical_coordinate() {
1938        let policy = ProjectionPolicy::new(AbsoluteBits::new(20));
1939        let values = failing_matrix(2, 2, &[1, 2, 3, 4], FailureStage::Divide);
1940
1941        assert_eq!(
1942            project_matrix_f64(&values, policy),
1943            Err(CertifiedLinearProjectionError::MatrixElement {
1944                row: 0,
1945                column: 0,
1946                source: ScalarProjectionError::FloatOutOfRange,
1947            })
1948        );
1949    }
1950
1951    #[test]
1952    fn from_row_major_reports_the_storage_length_payload() {
1953        assert_eq!(
1954            ExactMatrix::<u8>::from_row_major(Shape::new(2, 2), vec![1, 2, 3]),
1955            Err(super::ExactLinearError::Linear(
1956                neco_linear_types::LinearError::StorageLengthMismatch {
1957                    expected: 4,
1958                    actual: 3,
1959                }
1960            ))
1961        );
1962    }
1963
1964    #[test]
1965    fn determinant_reports_the_non_square_shape_payload() {
1966        let values = matrix(2, 3, &[1, 2, 3, 4, 5, 6]);
1967        assert_eq!(
1968            values.determinant(),
1969            Err(super::ExactLinearError::NonSquareMatrix {
1970                rows: 2,
1971                columns: 3,
1972            })
1973        );
1974    }
1975
1976    #[test]
1977    fn solve_reports_the_right_hand_side_length_payload() {
1978        let values = matrix(2, 2, &[1, 0, 0, 1]);
1979        assert_eq!(
1980            values.solve(&vector(&[1])),
1981            Err(super::ExactLinearError::Linear(
1982                neco_linear_types::LinearError::StorageLengthMismatch {
1983                    expected: 2,
1984                    actual: 1,
1985                }
1986            ))
1987        );
1988    }
1989
1990    #[test]
1991    fn determinant_preserves_a_pivot_normalization_failure() {
1992        let values = failing_matrix(1, 1, &[1], FailureStage::Divide);
1993        assert_eq!(
1994            values.determinant(),
1995            Err(super::ExactLinearError::Linear(
1996                neco_linear_types::LinearError::InvalidStorage {
1997                    reason: "test exact scalar division failure",
1998                }
1999            ))
2000        );
2001    }
2002
2003    #[test]
2004    fn solve_preserves_a_row_elimination_failure() {
2005        let values = failing_matrix(2, 1, &[1, 1], FailureStage::Multiply);
2006        let rhs = failing_vector(&[1, 1], FailureStage::Multiply);
2007        assert_eq!(
2008            values.solve(&rhs),
2009            Err(super::ExactLinearError::Linear(
2010                neco_linear_types::LinearError::InvalidStorage {
2011                    reason: "test exact scalar multiplication failure",
2012                }
2013            ))
2014        );
2015    }
2016
2017    #[test]
2018    fn scalar_failure_preserves_a_coefficient_clone_failure() {
2019        let values = failing_matrix(1, 1, &[1], FailureStage::Clone);
2020        let rhs = failing_vector(&[1], FailureStage::Clone);
2021        assert_eq!(
2022            values.solve(&rhs),
2023            Err(super::ExactLinearError::Linear(
2024                neco_linear_types::LinearError::InvalidStorage {
2025                    reason: "test exact scalar clone failure",
2026                }
2027            ))
2028        );
2029    }
2030
2031    #[test]
2032    fn determinant_and_rank_use_exact_rationals() {
2033        let values = matrix(2, 2, &[2, 1, 5, 3]);
2034        assert_eq!(values.determinant().expect("determinant"), integer(1));
2035        assert_eq!(values.rank().expect("rank"), 2);
2036    }
2037
2038    #[test]
2039    fn kernel_basis_uses_free_columns_in_ascending_order() {
2040        let values = matrix(2, 3, &[1, 2, 3, 2, 4, 6]);
2041        let basis = values.kernel_basis().expect("kernel basis");
2042        assert_eq!(basis.len(), 2);
2043        assert_eq!(basis[0].values(), &[integer(-2), integer(1), integer(0)]);
2044        assert_eq!(basis[1].values(), &[integer(-3), integer(0), integer(1)]);
2045    }
2046
2047    #[test]
2048    fn solve_returns_a_unique_solution() {
2049        let values = matrix(2, 2, &[2, 1, 5, 3]);
2050        let solution = values.solve(&vector(&[1, 2])).expect("solution");
2051        assert_eq!(solution, ExactLinearSolution::Unique(vector(&[1, -1])));
2052    }
2053
2054    #[test]
2055    fn solve_returns_an_affine_solution() {
2056        let values = matrix(1, 2, &[1, 1]);
2057        let solution = values.solve(&vector(&[3])).expect("solution");
2058        assert_eq!(
2059            solution,
2060            ExactLinearSolution::Affine {
2061                particular: vector(&[3, 0]),
2062                kernel: vec![vector(&[-1, 1])],
2063            }
2064        );
2065    }
2066
2067    #[test]
2068    fn solve_returns_inconsistent_for_a_contradictory_system() {
2069        let values = matrix(2, 1, &[1, 1]);
2070        assert_eq!(
2071            values.solve(&vector(&[1, 2])).expect("solution"),
2072            ExactLinearSolution::Inconsistent
2073        );
2074    }
2075
2076    #[test]
2077    fn pivot_selection_produces_the_same_deterministic_result() {
2078        let values = matrix(3, 3, &[0, 1, 1, 1, 1, 0, 1, 0, 1]);
2079        let first = values.solve(&vector(&[3, 3, 2])).expect("solution");
2080        let second = values.solve(&vector(&[3, 3, 2])).expect("solution");
2081        assert_eq!(first, ExactLinearSolution::Unique(vector(&[1, 2, 1])));
2082        assert_eq!(first, second);
2083    }
2084
2085    #[test]
2086    fn form_sum_adapter_solves_an_invertible_one_by_one_matrix() {
2087        let one = FormSum::one().expect("one");
2088        let matrix =
2089            ExactMatrix::from_row_major(Shape::new(1, 1), vec![one]).expect("valid matrix");
2090        let rhs = Vector::try_from_vec(vec![FormSum::one().expect("one")]).expect("valid vector");
2091        let solution = matrix.solve(&rhs).expect("solution");
2092        assert!(
2093            matches!(solution, ExactLinearSolution::Unique(value) if value.values()[0] == FormSum::one().expect("one"))
2094        );
2095    }
2096
2097    #[test]
2098    fn real_algebraic_adapter_computes_an_invertible_one_by_one_determinant() {
2099        let one = RealAlgebraic::one().expect("one");
2100        let matrix =
2101            ExactMatrix::from_row_major(Shape::new(1, 1), vec![one]).expect("valid matrix");
2102        let determinant = matrix.determinant().expect("determinant");
2103        assert!(!determinant.is_zero());
2104    }
2105
2106    #[test]
2107    fn composability_uses_only_the_public_exact_linear_types() {
2108        fn fit_system<T: ExactScalar>(
2109            coefficients: ExactMatrix<T>,
2110            samples: &Vector<T>,
2111        ) -> Result<ExactLinearSolution<T>, super::ExactLinearError> {
2112            coefficients.solve(samples)
2113        }
2114
2115        assert_eq!(
2116            fit_system(matrix(2, 2, &[1, 0, 0, 1]), &vector(&[3, 5])),
2117            Ok(ExactLinearSolution::Unique(vector(&[3, 5])))
2118        );
2119    }
2120
2121    #[test]
2122    fn solve_reports_allocation_failure_from_try_vec_capacity() {
2123        super::INJECT_NEXT_ALLOCATION_FAILURE.with(|failure| failure.set(true));
2124        let values = matrix(1, 1, &[1]);
2125        let rhs = vector(&[1]);
2126        assert_eq!(
2127            values.solve(&rhs),
2128            Err(super::ExactLinearError::Linear(
2129                neco_linear_types::LinearError::AllocationFailure { requested: 1 },
2130            ))
2131        );
2132    }
2133}