1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Copyright © 2025 Niklas Siemer
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
//! This module includes functionality to compute several norms
//! defined on matrices.
use super::MatPolynomialRingZq;
use crate::{
integer::Z,
rational::Q,
traits::{MatrixDimensions, MatrixGetSubmatrix},
};
impl MatPolynomialRingZq {
/// Outputs the squared l_{2, ∞}-norm, i.e. it computes the squared Euclidean
/// norm of each column of the matrix and returns the largest one.
///
/// # Examples
/// ```
/// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
/// use std::str::FromStr;
///
/// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 7").unwrap();
/// let mat = MatPolyOverZ::from_str("[[1 2, 1 3],[1 2, 0]]").unwrap();
/// let mat = MatPolynomialRingZq::from((&mat, &modulus));
///
/// let eucl_norm = mat.norm_l_2_infty_sqrd();
///
/// // 3^2 + 0^2 = 9
/// assert_eq!(Z::from(9), eucl_norm);
/// ```
pub fn norm_l_2_infty_sqrd(&self) -> Z {
let mut max_sqrd_norm = Z::ZERO;
for i in 0..self.get_num_columns() {
let column = unsafe { self.get_column_unchecked(i) };
let sqrd_norm = column.norm_eucl_sqrd().unwrap();
if sqrd_norm > max_sqrd_norm {
max_sqrd_norm = sqrd_norm;
}
}
max_sqrd_norm
}
/// Outputs the l_{2, ∞}-norm, i.e. it computes the Euclidean
/// norm of each column of the matrix and returns the largest one.
///
/// # Examples
/// ```
/// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
/// use std::str::FromStr;
/// # use qfall_math::rational::Q;
///
/// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 5").unwrap();
/// let mat = MatPolyOverZ::from_str("[[1 2, 1 3],[1 2, 1 0],[1 3, 1 4],[1 3, 1 4]]").unwrap();
/// let mat = MatPolynomialRingZq::from((&mat, &modulus));
///
/// let eucl_norm = mat.norm_l_2_infty();
///
/// // sqrt(4 * 2^2) = 4
/// assert_eq!(Q::from(4), eucl_norm);
/// ```
pub fn norm_l_2_infty(&self) -> Q {
self.norm_l_2_infty_sqrd().sqrt()
}
/// Outputs the l_{∞, ∞}-norm, i.e. it computes the ∞-norm
/// of each column of the matrix and returns the largest one.
///
/// # Examples
/// ```
/// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
/// use std::str::FromStr;
///
/// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 7").unwrap();
/// let mat = MatPolyOverZ::from_str("[[1 2, 1 4],[1 2, 0]]").unwrap();
/// let mat = MatPolynomialRingZq::from((&mat, &modulus));
///
/// let eucl_norm = mat.norm_l_infty_infty();
///
/// // max{2, 3} = 3
/// assert_eq!(Z::from(3), eucl_norm);
/// ```
pub fn norm_l_infty_infty(&self) -> Z {
let mut max_norm = Z::ZERO;
for i in 0..self.get_num_columns() {
let column = unsafe { self.get_column_unchecked(i) };
let norm = column.norm_infty().unwrap();
if norm > max_norm {
max_norm = norm;
}
}
max_norm
}
}
#[cfg(test)]
mod test_matrix_norms {
use super::{MatPolynomialRingZq, Q, Z};
use crate::{integer::MatPolyOverZ, integer_mod_q::ModulusPolynomialRingZq};
use std::str::FromStr;
/// Ensures that the squared l_{2, ∞}-norm is correctly computed.
#[test]
fn norm_sqrd_l_2_infty() {
let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 9").unwrap();
let mat = MatPolyOverZ::from_str(
"[[1 3, 1 -2, 1 5],[1 -5, 1 -6, 2 1 1],[1 -4, 0, 0],[1 2, 0, 3 1 1 1]]",
)
.unwrap();
let mat = MatPolynomialRingZq::from((&mat, &modulus));
let sqrd_norm = mat.norm_l_2_infty_sqrd();
assert_eq!(Z::from(45), sqrd_norm);
}
/// Ensures that the l_{2, ∞}-norm is correctly computed.
#[test]
fn norm_l_2_infty() {
let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 5").unwrap();
let mat =
MatPolyOverZ::from_str("[[1 -2, 4 -2 0 0 1],[1 -2, 1 -3],[1 -2, 0],[1 2, 0]]")
.unwrap();
let mat = MatPolynomialRingZq::from((&mat, &modulus));
let norm = mat.norm_l_2_infty();
assert_eq!(Q::from(4), norm);
}
/// Ensures that the l_{∞, ∞}-norm is correctly computed.
#[test]
fn norm_l_infty_infty() {
let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 8").unwrap();
let mat = MatPolyOverZ::from_str("[[2 -2 1, 1 3],[1 2, 1 -5],[1 -2, 0]]").unwrap();
let mat = MatPolynomialRingZq::from((&mat, &modulus));
let infty_norm = mat.norm_l_infty_infty();
assert_eq!(Z::from(3), infty_norm);
}
}