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 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}