1use ndarray::{Array1, Array2, Axis};
5use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};
6
7#[derive(Clone, Debug)]
17pub enum PenaltyMatrix {
18 Dense(Array2<f64>),
19 KroneckerFactored {
20 left: Array2<f64>,
21 right: Array2<f64>,
22 },
23 Blockwise {
27 local: Array2<f64>,
28 col_range: std::ops::Range<usize>,
29 total_dim: usize,
30 },
31 Labeled {
34 label: String,
35 inner: Box<PenaltyMatrix>,
36 },
37 Fixed {
41 log_lambda: f64,
42 inner: Box<PenaltyMatrix>,
43 },
44}
45
46impl PenaltyMatrix {
47 pub fn dim(&self) -> usize {
49 match self {
50 Self::Dense(m) => m.nrows(),
51 Self::KroneckerFactored { left, right } => left.nrows() * right.nrows(),
52 Self::Blockwise { total_dim, .. } => *total_dim,
53 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => inner.dim(),
54 }
55 }
56
57 pub fn shape(&self) -> (usize, usize) {
63 match self {
64 Self::Dense(m) => m.dim(),
65 Self::KroneckerFactored { left, right } => {
66 (left.nrows() * right.nrows(), left.ncols() * right.ncols())
67 }
68 Self::Blockwise { total_dim, .. } => (*total_dim, *total_dim),
69 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => inner.shape(),
70 }
71 }
72
73 pub fn validate(&self, expected_dim: usize) -> Result<(), String> {
86 let (nrows, ncols) = self.shape();
87 if nrows != ncols || nrows != expected_dim {
88 return Err(format!(
89 "penalty must be {expected_dim}x{expected_dim}, got {nrows}x{ncols}"
90 ));
91 }
92 match self {
93 Self::Dense(m) => validate_symmetric_psd_core(m, "dense penalty"),
94 Self::KroneckerFactored { left, right } => {
95 validate_symmetric_psd_core(left, "Kronecker left factor")?;
100 validate_symmetric_psd_core(right, "Kronecker right factor")
101 }
102 Self::Blockwise {
103 local,
104 col_range,
105 total_dim,
106 } => {
107 if col_range.end > *total_dim || col_range.len() != local.nrows() {
108 return Err(format!(
109 "blockwise penalty embedding is inconsistent: local {}x{} at columns \
110 {}..{} of total_dim {}",
111 local.nrows(),
112 local.ncols(),
113 col_range.start,
114 col_range.end,
115 total_dim
116 ));
117 }
118 validate_symmetric_psd_core(local, "blockwise local penalty")
119 }
120 Self::Labeled { inner, .. } => inner.validate(expected_dim),
121 Self::Fixed { log_lambda, inner } => {
122 if !log_lambda.is_finite() {
123 return Err(format!(
124 "fixed penalty log-precision is non-finite: {log_lambda}"
125 ));
126 }
127 inner.validate(expected_dim)
128 }
129 }
130 }
131
132 pub fn to_dense(&self) -> Array2<f64> {
134 match self {
135 Self::Dense(m) => m.clone(),
136 Self::KroneckerFactored { left, right } => kronecker_product(left, right),
137 Self::Blockwise {
138 local,
139 col_range,
140 total_dim,
141 } => {
142 let mut g = Array2::zeros((*total_dim, *total_dim));
143 g.slice_mut(ndarray::s![
144 col_range.start..col_range.end,
145 col_range.start..col_range.end
146 ])
147 .assign(local);
148 g
149 }
150 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => inner.to_dense(),
151 }
152 }
153
154 pub fn as_dense_cow(&self) -> std::borrow::Cow<'_, Array2<f64>> {
156 match self {
157 Self::Dense(m) => std::borrow::Cow::Borrowed(m),
158 Self::KroneckerFactored { .. }
159 | Self::Blockwise { .. }
160 | Self::Labeled { .. }
161 | Self::Fixed { .. } => std::borrow::Cow::Owned(self.to_dense()),
162 }
163 }
164
165 pub fn as_dense_ref(&self) -> Option<&Array2<f64>> {
167 match self {
168 Self::Dense(m) => Some(m),
169 Self::Fixed { inner, .. } => inner.as_dense_ref(),
170 Self::KroneckerFactored { .. } | Self::Blockwise { .. } | Self::Labeled { .. } => None,
171 }
172 }
173
174 pub fn with_precision_label(self, label: impl Into<String>) -> Self {
175 Self::Labeled {
176 label: label.into(),
177 inner: Box::new(self),
178 }
179 }
180
181 pub fn precision_label(&self) -> Option<&str> {
182 match self {
183 Self::Labeled { label, .. } => Some(label.as_str()),
184 Self::Fixed { .. } => None,
185 _ => None,
186 }
187 }
188
189 pub fn with_fixed_log_lambda(self, log_lambda: f64) -> Self {
190 Self::Fixed {
191 log_lambda,
192 inner: Box::new(self),
193 }
194 }
195
196 pub fn fixed_log_lambda(&self) -> Option<f64> {
197 match self {
198 Self::Fixed { log_lambda, .. } => Some(*log_lambda),
199 Self::Labeled { inner, .. } => inner.fixed_log_lambda(),
200 _ => None,
201 }
202 }
203
204 pub fn dot(&self, v: &Array1<f64>) -> Array1<f64> {
208 match self {
209 Self::Dense(m) => m.dot(v),
210 Self::KroneckerFactored { left, right } => {
211 let p_left = left.nrows();
212 let p_right = right.nrows();
213 let v_mat =
215 ndarray::ArrayView2::from_shape((p_left, p_right), v.as_slice().unwrap())
216 .unwrap();
217 let avbt = left.dot(&v_mat).dot(&right.t());
218 let standard = avbt.as_standard_layout();
219 Array1::from_iter(standard.iter().copied())
220 }
221 Self::Blockwise {
222 local,
223 col_range,
224 total_dim,
225 } => {
226 let mut out = Array1::zeros(*total_dim);
227 let v_block = v.slice(ndarray::s![col_range.clone()]);
228 let result_block = local.dot(&v_block);
229 out.slice_mut(ndarray::s![col_range.clone()])
230 .assign(&result_block);
231 out
232 }
233 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => inner.dot(v),
234 }
235 }
236
237 pub fn add_scaled_to(&self, lambda: f64, target: &mut Array2<f64>) {
239 match self {
240 Self::Dense(m) => {
241 target.scaled_add(lambda, m);
242 }
243 Self::KroneckerFactored { left, right } => {
244 let p_left = left.nrows();
245 let p_right = right.nrows();
246 for i1 in 0..p_left {
247 for j1 in 0..p_left {
248 let a_ij = left[[i1, j1]];
249 if a_ij == 0.0 {
250 continue;
251 }
252 let scaled_a = lambda * a_ij;
253 for i2 in 0..p_right {
254 let row = i1 * p_right + i2;
255 for j2 in 0..p_right {
256 let col = j1 * p_right + j2;
257 target[[row, col]] += scaled_a * right[[i2, j2]];
258 }
259 }
260 }
261 }
262 }
263 Self::Blockwise {
264 local, col_range, ..
265 } => {
266 target
267 .slice_mut(ndarray::s![col_range.clone(), col_range.clone()])
268 .scaled_add(lambda, local);
269 }
270 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => {
271 inner.add_scaled_to(lambda, target)
272 }
273 }
274 }
275
276 pub fn add_scaled_diag_to(&self, lambda: f64, target: &mut Array1<f64>) {
278 match self {
279 Self::Dense(m) => {
280 let p = m.nrows().min(target.len());
281 for j in 0..p {
282 target[j] += lambda * m[[j, j]];
283 }
284 }
285 Self::KroneckerFactored { left, right } => {
286 let p_left = left.nrows();
287 let p_right = right.nrows();
288 assert_eq!(target.len(), p_left * p_right);
289 for i_left in 0..p_left {
290 let left_diag = left[[i_left, i_left]];
291 if left_diag == 0.0 {
292 continue;
293 }
294 let scaled_left = lambda * left_diag;
295 for i_right in 0..p_right {
296 target[i_left * p_right + i_right] +=
297 scaled_left * right[[i_right, i_right]];
298 }
299 }
300 }
301 Self::Blockwise {
302 local, col_range, ..
303 } => {
304 let width = local.nrows().min(col_range.len());
305 for local_idx in 0..width {
306 target[col_range.start + local_idx] += lambda * local[[local_idx, local_idx]];
307 }
308 }
309 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => {
310 inner.add_scaled_diag_to(lambda, target)
311 }
312 }
313 }
314
315 pub fn quadratic_form(&self, beta: &Array1<f64>) -> f64 {
317 match self {
318 Self::Dense(m) => beta.dot(&m.dot(beta)),
319 Self::KroneckerFactored { .. } => {
320 let sv = self.dot(beta);
321 beta.dot(&sv)
322 }
323 Self::Blockwise {
324 local, col_range, ..
325 } => {
326 let beta_block = beta.slice(ndarray::s![col_range.clone()]);
327 let sv = local.dot(&beta_block);
328 beta_block.dot(&sv)
329 }
330 Self::Labeled { inner, .. } | Self::Fixed { inner, .. } => inner.quadratic_form(beta),
331 }
332 }
333
334 pub fn nrows(&self) -> usize {
336 self.dim()
337 }
338
339 pub fn ncols(&self) -> usize {
340 self.dim()
341 }
342}
343
344impl From<Array2<f64>> for PenaltyMatrix {
345 fn from(m: Array2<f64>) -> Self {
346 Self::Dense(m)
347 }
348}
349
350fn validate_symmetric_psd_core(matrix: &Array2<f64>, what: &str) -> Result<(), String> {
356 use gam_linalg::faer_ndarray::FaerEigh;
357
358 let (nrows, ncols) = matrix.dim();
359 if nrows != ncols {
360 return Err(format!("{what} is not square: {nrows}x{ncols}"));
361 }
362 let mut max_abs = 0.0_f64;
363 for ((row, col), &value) in matrix.indexed_iter() {
364 if !value.is_finite() {
365 return Err(format!(
366 "{what} has non-finite entry at ({row},{col}): {value}"
367 ));
368 }
369 max_abs = max_abs.max(value.abs());
370 }
371 let sym_tol = 1e-10 * max_abs.max(1.0);
374 for row in 0..nrows {
375 for col in (row + 1)..ncols {
376 let asymmetry = (matrix[[row, col]] - matrix[[col, row]]).abs();
377 if asymmetry > sym_tol {
378 return Err(format!(
379 "{what} is not symmetric at ({row},{col}): |S - Sᵀ| = {asymmetry:.3e}; \
380 the gradient of βᵀSβ/2 is sym(S)β, so a skew component would make the \
381 implemented objective and gradient describe different functions"
382 ));
383 }
384 }
385 }
386 if nrows == 0 || max_abs == 0.0 {
387 return Ok(()); }
389 let (eigenvalues, _) = matrix
390 .eigh(faer::Side::Lower)
391 .map_err(|e| format!("{what} eigendecomposition failed during validation: {e}"))?;
392 let max_abs_eval = eigenvalues
393 .iter()
394 .fold(0.0_f64, |acc, &ev| acc.max(ev.abs()));
395 let psd_tol = 100.0 * (nrows as f64) * f64::EPSILON * max_abs_eval;
396 if let Some(&min_eval) = eigenvalues
397 .iter()
398 .filter(|&&ev| ev < -psd_tol)
399 .min_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
400 {
401 return Err(format!(
402 "{what} is not positive semidefinite: min eigenvalue {min_eval:.6e} \
403 (max |eigenvalue| {max_abs_eval:.6e}); the penalized objective is unbounded \
404 below along the negative mode while rank/logdet filtering would silently \
405 drop it"
406 ));
407 }
408 Ok(())
409}
410
411fn kronecker_product(a: &Array2<f64>, b: &Array2<f64>) -> Array2<f64> {
415 let (arows, a_cols) = a.dim();
416 let (brows, b_cols) = b.dim();
417 if arows == 0 || a_cols == 0 || brows == 0 || b_cols == 0 {
418 return Array2::zeros((arows * brows, a_cols * b_cols));
419 }
420 let mut result = Array2::zeros((arows * brows, a_cols * b_cols));
421
422 result
423 .axis_chunks_iter_mut(Axis(0), brows)
424 .into_par_iter()
425 .enumerate()
426 .for_each(|(i, mut row_block)| {
427 let arow = a.row(i);
428 let col_chunks = row_block.axis_chunks_iter_mut(Axis(1), b_cols);
429 for (j, mut block) in col_chunks.into_iter().enumerate() {
430 let aval = arow[j];
431 if aval == 0.0 {
432 continue;
433 }
434 for (dest, &src) in block.iter_mut().zip(b.iter()) {
435 *dest = aval * src;
436 }
437 }
438 });
439
440 result
441}
442
443#[cfg(test)]
444mod tests {
445 use super::*;
446 use ndarray::array;
447
448 #[test]
451 fn dense_dim_and_shape() {
452 let m = array![[1.0, 0.0], [0.0, 2.0]];
453 let p = PenaltyMatrix::Dense(m);
454 assert_eq!(p.dim(), 2);
455 assert_eq!(p.shape(), (2, 2));
456 assert_eq!(p.nrows(), 2);
457 assert_eq!(p.ncols(), 2);
458 }
459
460 #[test]
461 fn dense_to_dense_is_clone() {
462 let m = array![[3.0, 1.0], [1.0, 4.0]];
463 let p = PenaltyMatrix::Dense(m.clone());
464 assert_eq!(p.to_dense(), m);
465 }
466
467 #[test]
468 fn dense_dot_product() {
469 let m = array![[1.0, 0.0], [0.0, 2.0]];
471 let p = PenaltyMatrix::Dense(m);
472 let v = ndarray::array![3.0, 5.0];
473 let result = p.dot(&v);
474 assert_eq!(result.as_slice().unwrap(), &[3.0, 10.0]);
475 }
476
477 #[test]
478 fn dense_quadratic_form() {
479 let m = array![[1.0, 0.0], [0.0, 2.0]];
481 let p = PenaltyMatrix::Dense(m);
482 let beta = ndarray::array![3.0, 2.0];
483 assert!((p.quadratic_form(&beta) - 17.0).abs() < 1e-14);
484 }
485
486 #[test]
487 fn dense_add_scaled_to() {
488 let s = array![[1.0, 0.0], [0.0, 1.0]];
489 let p = PenaltyMatrix::Dense(s);
490 let mut acc = ndarray::Array2::<f64>::zeros((2, 2));
491 p.add_scaled_to(3.0, &mut acc);
492 assert_eq!(acc, array![[3.0, 0.0], [0.0, 3.0]]);
493 }
494
495 #[test]
496 fn dense_add_scaled_diag_to() {
497 let s = array![[2.0, 5.0], [5.0, 7.0]];
498 let p = PenaltyMatrix::Dense(s);
499 let mut diag = ndarray::array![0.0, 0.0];
500 p.add_scaled_diag_to(1.0, &mut diag);
501 assert_eq!(diag.as_slice().unwrap(), &[2.0, 7.0]);
503 }
504
505 #[test]
508 fn kronecker_dim_is_product() {
509 let left = array![[1.0, 0.0], [0.0, 1.0]]; let right = array![[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]]; let p = PenaltyMatrix::KroneckerFactored { left, right };
512 assert_eq!(p.dim(), 6);
513 }
514
515 #[test]
516 fn kronecker_to_dense_identity_x_identity() {
517 let eye2 = ndarray::Array2::<f64>::eye(2);
519 let p = PenaltyMatrix::KroneckerFactored {
520 left: eye2.clone(),
521 right: eye2,
522 };
523 let dense = p.to_dense();
524 assert_eq!(dense, ndarray::Array2::<f64>::eye(4));
525 }
526
527 #[test]
528 fn kronecker_dot_matches_dense_dot() {
529 let left = array![[2.0, 0.0], [0.0, 3.0]];
530 let right = array![[1.0, 1.0], [0.0, 1.0]];
531 let p = PenaltyMatrix::KroneckerFactored {
532 left: left.clone(),
533 right: right.clone(),
534 };
535 let dense = p.to_dense();
537 let v = ndarray::array![1.0, 2.0, 3.0, 4.0];
538 let got = p.dot(&v);
539 let expected = dense.dot(&v);
540 for (a, b) in got.iter().zip(expected.iter()) {
541 assert!((a - b).abs() < 1e-14, "got={a} expected={b}");
542 }
543 }
544
545 #[test]
548 fn blockwise_dim_is_total() {
549 let local = array![[1.0, 0.0], [0.0, 1.0]];
550 let p = PenaltyMatrix::Blockwise {
551 local,
552 col_range: 1..3,
553 total_dim: 5,
554 };
555 assert_eq!(p.dim(), 5);
556 }
557
558 #[test]
559 fn blockwise_to_dense_embeds_local_block() {
560 let local = array![[2.0, 1.0], [1.0, 3.0]];
562 let p = PenaltyMatrix::Blockwise {
563 local,
564 col_range: 1..3,
565 total_dim: 3,
566 };
567 let dense = p.to_dense();
568 assert_eq!(dense[[0, 0]], 0.0);
569 assert_eq!(dense[[1, 1]], 2.0);
570 assert_eq!(dense[[1, 2]], 1.0);
571 assert_eq!(dense[[2, 1]], 1.0);
572 assert_eq!(dense[[2, 2]], 3.0);
573 }
574
575 #[test]
576 fn blockwise_dot_only_touches_block() {
577 let local = array![[2.0, 0.0], [0.0, 3.0]];
578 let p = PenaltyMatrix::Blockwise {
579 local,
580 col_range: 1..3,
581 total_dim: 4,
582 };
583 let v = ndarray::array![7.0, 1.0, 2.0, 9.0];
584 let out = p.dot(&v);
585 assert_eq!(out.as_slice().unwrap(), &[0.0, 2.0, 6.0, 0.0]);
587 }
588
589 #[test]
592 fn labeled_inherits_dim_and_delegates_dot() {
593 let m = array![[1.0, 0.0], [0.0, 2.0]];
594 let p = PenaltyMatrix::Dense(m).with_precision_label("smooth");
595 assert_eq!(p.dim(), 2);
596 assert_eq!(p.precision_label(), Some("smooth"));
597 let v = ndarray::array![3.0, 4.0];
598 let out = p.dot(&v);
599 assert_eq!(out.as_slice().unwrap(), &[3.0, 8.0]);
600 }
601
602 #[test]
603 fn fixed_inherits_dim_and_exposes_log_lambda() {
604 let m = array![[5.0, 0.0], [0.0, 5.0]];
605 let p = PenaltyMatrix::Dense(m).with_fixed_log_lambda(2.5);
606 assert_eq!(p.dim(), 2);
607 assert_eq!(p.fixed_log_lambda(), Some(2.5));
608 }
609
610 #[test]
613 fn shape_reports_actual_storage_not_fabricated_square() {
614 let p = PenaltyMatrix::Dense(Array2::<f64>::zeros((2, 3)));
617 assert_eq!(p.shape(), (2, 3));
618 assert!(p.validate(2).is_err());
619 assert!(p.validate(3).is_err());
620 }
621
622 #[test]
623 fn validate_accepts_canonical_carriers() {
624 let dense = PenaltyMatrix::Dense(array![[2.0, -1.0], [-1.0, 2.0]]);
625 assert_eq!(dense.validate(2), Ok(()));
626
627 let kron = PenaltyMatrix::KroneckerFactored {
628 left: array![[1.0, -1.0], [-1.0, 1.0]],
629 right: ndarray::Array2::<f64>::eye(3),
630 };
631 assert_eq!(kron.validate(6), Ok(()));
632
633 let blockwise = PenaltyMatrix::Blockwise {
634 local: array![[1.0, 0.0], [0.0, 1.0]],
635 col_range: 1..3,
636 total_dim: 4,
637 };
638 assert_eq!(blockwise.validate(4), Ok(()));
639 }
640
641 #[test]
642 fn validate_rejects_asymmetric_indefinite_and_nonfinite() {
643 let skew = PenaltyMatrix::Dense(array![[1.0, 1.0], [0.0, 1.0]]);
645 assert!(skew.validate(2).unwrap_err().contains("not symmetric"));
646
647 let indefinite = PenaltyMatrix::Dense(array![[1.0, 0.0], [0.0, -1.0]]);
649 assert!(
650 indefinite
651 .validate(2)
652 .unwrap_err()
653 .contains("not positive semidefinite")
654 );
655
656 let nan = PenaltyMatrix::Dense(array![[f64::NAN, 0.0], [0.0, 1.0]]);
657 assert!(nan.validate(2).unwrap_err().contains("non-finite"));
658
659 let bad_fixed = PenaltyMatrix::Dense(ndarray::Array2::<f64>::eye(2))
661 .with_fixed_log_lambda(f64::INFINITY);
662 assert!(bad_fixed.validate(2).unwrap_err().contains("non-finite"));
663 }
664
665 #[test]
666 fn validate_rejects_inconsistent_blockwise_embedding() {
667 let p = PenaltyMatrix::Blockwise {
669 local: ndarray::Array2::<f64>::eye(3),
670 col_range: 1..3,
671 total_dim: 4,
672 };
673 assert!(p.validate(4).is_err());
674 let q = PenaltyMatrix::Blockwise {
676 local: ndarray::Array2::<f64>::eye(2),
677 col_range: 3..5,
678 total_dim: 4,
679 };
680 assert!(q.validate(4).is_err());
681 }
682}