Module vector_norms

Expand description

Functions and utilities for computing vector norms.

This module provides public utilities for vector-norm computation on validated scalars (ScalarType: FpScalar), supporting both real (RealScalar) and complex (ComplexScalar) scalars.

§Norm type structs

Three zero-sized structs identify norm kinds and implement the VectorNorm and ParallelVectorNorm traits:

Struct	Formula	Accumulator
`L1Norm<Acc>`	`‖v‖₁ = Σᵢ \|vᵢ\|`	`SumAccumulator`
`L2Norm<Acc>`	`‖v‖₂ = √(Σᵢ \|vᵢ\|²)`	`SumAccumulator`
`LinfNorm<Acc>`	`‖v‖∞ = maxᵢ \|vᵢ\|`	`MaxAbsValueAccumulator`

The type parameter Acc selects the summation strategy:

NaiveSum<R> — fast plain += (default for most functions)
NeumaierSum<R> — compensated summation for higher accuracy

For the two most common combinations, convenience type aliases are provided:

Alias	Expands to
`L1NormNaiveSum<T>`	`L1Norm<NaiveSum<T::RealType>>`
`L1NormNeumaierSum<T>`	`L1Norm<NeumaierSum<T::RealType>>`
`L2NormNaiveSum<T>`	`L2Norm<NaiveSum<T::RealType>>`
`L2NormNeumaierSum<T>`	`L2Norm<NeumaierSum<T::RealType>>`

§Direct usage

The structs can be used directly via their static methods — useful when you need a specific norm+strategy combination without going through the free functions. The type aliases make the type annotations shorter:

use num_valid::algorithms::vector_norms::{
    L1Norm, L2Norm, LinfNorm, VectorNorm, ParallelVectorNorm,
    L1NormNaiveSum, L2NormNaiveSum, L2NormNeumaierSum,
};
use num_valid::algorithms::accumulators::{NaiveSum, NeumaierSum};

let v = [3.0_f64, -4.0, 5.0];

// Using a type alias — equivalent to L1Norm::<NaiveSum<f64>>::compute_vector_norm(&v)
let l1 = L1NormNaiveSum::<f64>::compute_vector_norm(&v);
assert_eq!(*l1.as_ref(), 12.0);

// L2 norm with Neumaier compensated summation (higher accuracy)
let l2 = L2NormNeumaierSum::<f64>::compute_vector_norm(&v);
assert!((*l2.as_ref() - 50.0_f64.sqrt()).abs() < 1e-12);

// L∞ norm (default marker type `Acc = ()`)
let linf = LinfNorm::<()>::compute_vector_norm(&v);
assert_eq!(*linf.as_ref(), 5.0);

// L∞ norm in parallel
let linf_par = LinfNorm::<()>::compute_vector_norm_par(&v);
assert_eq!(linf_par, linf);

// L2 squared norm (not a norm, but avoids the sqrt)
let l2_sq = L2NormNaiveSum::<f64>::compute_vector_norm_sq(&v);
assert_eq!(*l2_sq.as_ref(), 50.0);

§Trait-based API

VectorNorm<ScalarType> and ParallelVectorNorm<T> provide a generic interface that lets algorithms be parameterised over the norm type:

use num_valid::algorithms::vector_norms::{VectorNorm, L2Norm};
use num_valid::algorithms::accumulators::NaiveSum;
use num_valid::FpScalar;
use num_valid::scalars::NonNegativeRealScalar;

fn compute<T: FpScalar, N: VectorNorm<T>>(data: &[T]) -> NonNegativeRealScalar<T::RealType> {
    N::compute_vector_norm(data)
}

let v = [3.0_f64, 4.0];
let norm = compute::<_, L2Norm<NaiveSum<f64>>>(&v);
assert!((*norm.as_ref() - 5.0).abs() < 1e-12);

§Free functions

Ergonomic wrappers for the most common use cases. All variants accept both slice (&[ScalarType]) and owned-iterator (_iter-suffixed) inputs. All return NonNegativeRealScalar<ScalarType::RealType>.

For real scalars RealType = ScalarType; for complex scalars RealType is the underlying real component type — the norm is always real-valued because each element contributes via its modulus |·|.

When the input is borrowed (e.g. slice.iter()), chain .cloned() before passing to an _iter-suffixed function.

§L2 (Euclidean) norms — `‖v‖₂ = √(Σᵢ |vᵢ|²)`

Function	Formula	Summation
`vector_norm_l2`	`‖v‖₂`	naive
`vector_norm_l2_iter`	`‖v‖₂`	naive
`vector_norm_l2_neumaier`	`‖v‖₂`	Neumaier compensated
`vector_norm_l2_neumaier_iter`	`‖v‖₂`	Neumaier compensated
`vector_norm_l2_sq`	`‖v‖₂²`	naive
`vector_norm_l2_sq_iter`	`‖v‖₂²`	naive
`vector_norm_l2_sq_neumaier`	`‖v‖₂²`	Neumaier compensated
`vector_norm_l2_sq_neumaier_iter`	`‖v‖₂²`	Neumaier compensated

All L2 variants use a scaled sum-of-squares algorithm (equivalent to LAPACK dnrm2): the running scale = max |vᵢ| ensures that no intermediate value overflows or underflows. The _neumaier variants additionally apply compensated summation to recover low-order bits lost when components span many orders of magnitude.

Note: ‖v‖₂² is not a norm (it violates the triangle inequality) and is therefore intentionally absent from the VectorNorm trait. It is exposed as a computational convenience and as a method on L2Norm.

§L1 (Manhattan) norm — `‖v‖₁ = Σᵢ |vᵢ|`

Function	Formula	Summation
`vector_norm_l1`	`‖v‖₁`	naive
`vector_norm_l1_iter`	`‖v‖₁`	naive
`vector_norm_l1_neumaier`	`‖v‖₁`	Neumaier compensated
`vector_norm_l1_neumaier_iter`	`‖v‖₁`	Neumaier compensated

§L∞ (Chebyshev) norm — `‖v‖∞ = maxᵢ |vᵢ|`

Function	Execution
`vector_norm_linf`	sequential, slice
`vector_norm_linf_iter`	sequential, iterator
`vector_norm_linf_par`	parallel, slice
`vector_norm_linf_par_iter`	parallel, iterator

§Advanced API — custom accumulator

For full control over the summation strategy use the accumulator-generic functions. These accept any SumAccumulator as a type parameter:

Structs§

L1Norm: Identifies the Manhattan (L1) norm, ‖v‖₁ = Σᵢ |vᵢ|.
L2Norm: Identifies the Euclidean (L2) norm, ‖v‖₂ = √(Σᵢ |vᵢ|²).
LinfNorm: Identifies the Chebyshev (L∞) norm, ‖v‖∞ = maxᵢ |vᵢ|.

Traits§

ParallelVectorNorm: Parallel vector norm computation.
VectorNorm: Sequential vector norm computation.

Functions§

vector_norm_l1: Computes the Manhattan (L1) norm of a slice of scalars.
vector_norm_l2: Computes the Euclidean (L2) norm of a slice of scalars.
vector_norm_l1_iter: Computes the Manhattan (L1) norm from an owned-item iterator.
vector_norm_l1_iter_with_accumulator: Iterator-based accumulator-driven implementation of the Manhattan (L1) norm.
vector_norm_l1_neumaier: Computes the Manhattan (L1) norm of a slice of scalars using Neumaier compensated summation.
vector_norm_l1_neumaier_iter: Computes the Manhattan (L1) norm from an owned-item iterator using Neumaier compensated summation.
vector_norm_l1_with_accumulator: Accumulator-driven implementation of the Manhattan (L1) norm.
vector_norm_l2_iter: Computes the Euclidean (L2) norm from an owned-item iterator.
vector_norm_l2_iter_with_accumulator: Iterator-based accumulator-driven implementation of the Euclidean (L2) norm.
vector_norm_l2_neumaier: Computes the Euclidean (L2) norm of a slice of scalars using scaling + Neumaier compensated summation.
vector_norm_l2_neumaier_iter: Computes the Euclidean (L2) norm from an owned-item iterator using scaling plus Neumaier compensated summation.
vector_norm_l2_sq: Computes the squared Euclidean (L2) norm of a slice of scalars.
vector_norm_l2_sq_iter: Computes the squared Euclidean (L2) norm from an owned-item iterator.
vector_norm_l2_sq_iter_with_accumulator: Iterator-based accumulator-driven implementation of the squared Euclidean (L2) norm.
vector_norm_l2_sq_neumaier: Computes the squared Euclidean (L2) norm of a slice of scalars using scaling + Neumaier compensated summation.
vector_norm_l2_sq_neumaier_iter: Computes the squared Euclidean (L2) norm from an owned-item iterator using scaling plus Neumaier compensated summation.
vector_norm_l2_sq_with_accumulator: Accumulator-driven implementation of the squared Euclidean (L2) norm.
vector_norm_l2_with_accumulator: Accumulator-driven implementation of the Euclidean (L2) norm.
vector_norm_linf: Computes the Chebyshev (L∞) norm of a slice of scalars.
vector_norm_linf_iter: Computes the Chebyshev (L∞) norm from an owned-item iterator.
vector_norm_linf_par: Computes the Chebyshev (L∞) norm of a slice of scalars in parallel.
vector_norm_linf_par_iter: Computes the infinity norm (maximum absolute value) of a parallel iterator of values.

Type Aliases§

L1NormNaiveSum: Type alias for L1Norm using NaiveSum as summation strategy.
L1NormNeumaierSum: Type alias for L1Norm using NeumaierSum as summation strategy.
L2NormNaiveSum: Type alias for L2Norm using NaiveSum as summation strategy.
L2NormNeumaierSum: Type alias for L2Norm using NeumaierSum as summation strategy.