1use xingo_sparse::{CscMatrix, CsrMatrix, DenseBlock, Real};
50
51use crate::view::{MatMut, MatRef};
52
53#[derive(Clone, Debug, PartialEq, Eq)]
57pub struct OperatorError {
58 pub message: String,
60}
61
62impl OperatorError {
63 fn new(message: &str) -> Self {
64 Self {
65 message: message.to_owned(),
66 }
67 }
68}
69
70fn check(x: usize, xe: usize, y: usize, ye: usize) -> Result<(), OperatorError> {
72 if x == xe && y == ye {
73 Ok(())
74 } else {
75 Err(OperatorError::new(
76 "operator applied to vectors of the wrong length",
77 ))
78 }
79}
80
81pub trait LinearOperator<T: Real = f64> {
90 fn nrows(&self) -> usize;
92 fn ncols(&self) -> usize;
94 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError>;
99 fn apply_block(&mut self, x: MatRef<'_, T>, mut y: MatMut<'_, T>) -> Result<(), OperatorError> {
108 check_block(
109 x.rows(),
110 self.ncols(),
111 y.rows(),
112 self.nrows(),
113 x.cols(),
114 y.cols(),
115 )?;
116 for c in 0..x.cols() {
117 let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
118 return Err(OperatorError::new("block column out of range"));
119 };
120 self.apply(xc, yc)?;
121 }
122 Ok(())
123 }
124}
125
126pub trait AdjointOperator<T: Real = f64>: LinearOperator<T> {
129 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError>;
134 fn apply_t_block(
140 &mut self,
141 x: MatRef<'_, T>,
142 mut y: MatMut<'_, T>,
143 ) -> Result<(), OperatorError> {
144 check_block(
145 x.rows(),
146 self.nrows(),
147 y.rows(),
148 self.ncols(),
149 x.cols(),
150 y.cols(),
151 )?;
152 for c in 0..x.cols() {
153 let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
154 return Err(OperatorError::new("block column out of range"));
155 };
156 self.apply_t(xc, yc)?;
157 }
158 Ok(())
159 }
160}
161
162fn check_block(
164 xr: usize,
165 xe: usize,
166 yr: usize,
167 ye: usize,
168 xc: usize,
169 yc: usize,
170) -> Result<(), OperatorError> {
171 if xr == xe && yr == ye && xc == yc {
172 Ok(())
173 } else {
174 Err(OperatorError::new(
175 "operator applied to blocks of the wrong shape",
176 ))
177 }
178}
179
180impl<T: Real, O: LinearOperator<T> + ?Sized> LinearOperator<T> for &mut O {
181 fn nrows(&self) -> usize {
182 (**self).nrows()
183 }
184 fn ncols(&self) -> usize {
185 (**self).ncols()
186 }
187 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
188 (**self).apply(x, y)
189 }
190 fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
191 (**self).apply_block(x, y)
192 }
193}
194
195impl<T: Real, O: AdjointOperator<T> + ?Sized> AdjointOperator<T> for &mut O {
196 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
197 (**self).apply_t(x, y)
198 }
199 fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
200 (**self).apply_t_block(x, y)
201 }
202}
203
204fn dense_apply<T: Real>(data: &[T], rows: usize, cols: usize, ld: usize, x: &[T], y: &mut [T]) {
209 y.fill(T::ZERO);
210 for k in 0..cols {
211 let xk = x[k];
212 let a = &data[k * ld..k * ld + rows];
213 for (yi, &aik) in y.iter_mut().zip(a) {
214 *yi += aik * xk;
215 }
216 }
217}
218
219fn dense_apply_t<T: Real>(data: &[T], rows: usize, cols: usize, ld: usize, x: &[T], y: &mut [T]) {
221 for (j, yj) in y.iter_mut().enumerate().take(cols) {
222 let a = &data[j * ld..j * ld + rows];
223 *yj = a.iter().zip(x).map(|(&p, &q)| p * q).sum();
224 }
225}
226
227fn dense_block<T: Real>(
229 data: &[T],
230 (rows, cols, ld): (usize, usize, usize),
231 transpose: bool,
232 x: MatRef<'_, T>,
233 mut y: MatMut<'_, T>,
234) -> Result<(), OperatorError> {
235 let (xe, ye) = if transpose {
236 (rows, cols)
237 } else {
238 (cols, rows)
239 };
240 check_block(x.rows(), xe, y.rows(), ye, x.cols(), y.cols())?;
241 for c in 0..x.cols() {
242 let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
243 return Err(OperatorError::new("block column out of range"));
244 };
245 if transpose {
246 dense_apply_t(data, rows, cols, ld, xc, yc);
247 } else {
248 dense_apply(data, rows, cols, ld, xc, yc);
249 }
250 }
251 Ok(())
252}
253
254fn block_parts<T: Real>(b: &DenseBlock<T>) -> Result<(usize, usize, usize), OperatorError> {
256 if b.data.len() == b.rows.saturating_mul(b.cols) {
257 Ok((b.rows, b.cols, b.rows))
258 } else {
259 Err(OperatorError::new(
260 "DenseBlock: data.len() differs from rows * cols",
261 ))
262 }
263}
264
265impl<T: Real> LinearOperator<T> for DenseBlock<T> {
267 fn nrows(&self) -> usize {
268 self.rows
269 }
270 fn ncols(&self) -> usize {
271 self.cols
272 }
273 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
274 let (r, c, ld) = block_parts(self)?;
275 check(x.len(), c, y.len(), r)?;
276 dense_apply(&self.data, r, c, ld, x, y);
277 Ok(())
278 }
279 fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
280 let parts = block_parts(self)?;
281 dense_block(&self.data, parts, false, x, y)
282 }
283}
284impl<T: Real> AdjointOperator<T> for DenseBlock<T> {
285 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
286 let (r, c, ld) = block_parts(self)?;
287 check(x.len(), r, y.len(), c)?;
288 dense_apply_t(&self.data, r, c, ld, x, y);
289 Ok(())
290 }
291 fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
292 let parts = block_parts(self)?;
293 dense_block(&self.data, parts, true, x, y)
294 }
295}
296
297impl<T: Real> LinearOperator<T> for MatRef<'_, T> {
299 fn nrows(&self) -> usize {
300 self.rows()
301 }
302 fn ncols(&self) -> usize {
303 self.cols()
304 }
305 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
306 check(x.len(), self.cols(), y.len(), self.rows())?;
307 dense_apply(self.raw(), self.rows(), self.cols(), self.ld(), x, y);
308 Ok(())
309 }
310 fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
311 let parts = (self.rows(), self.cols(), self.ld());
312 dense_block(self.raw(), parts, false, x, y)
313 }
314}
315impl<T: Real> AdjointOperator<T> for MatRef<'_, T> {
316 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
317 check(x.len(), self.rows(), y.len(), self.cols())?;
318 dense_apply_t(self.raw(), self.rows(), self.cols(), self.ld(), x, y);
319 Ok(())
320 }
321 fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
322 let parts = (self.rows(), self.cols(), self.ld());
323 dense_block(self.raw(), parts, true, x, y)
324 }
325}
326
327const BAD_SPARSE: &str = "sparse matrix with inconsistent fields (index out of range)";
330
331fn segment<'a, T>(
333 ptr: &[usize],
334 idx: &'a [u32],
335 val: &'a [T],
336 j: usize,
337) -> Result<(&'a [u32], &'a [T]), OperatorError> {
338 let (Some(&a), Some(&b)) = (ptr.get(j), ptr.get(j + 1)) else {
339 return Err(OperatorError::new(BAD_SPARSE));
340 };
341 match (idx.get(a..b), val.get(a..b)) {
342 (Some(i), Some(v)) => Ok((i, v)),
343 _ => Err(OperatorError::new(BAD_SPARSE)),
344 }
345}
346
347fn scatter<T: Real>(rows: &[u32], vals: &[T], t: T, y: &mut [T]) -> Result<(), OperatorError> {
349 for (&i, &v) in rows.iter().zip(vals) {
350 let Some(yi) = y.get_mut(i as usize) else {
351 return Err(OperatorError::new(BAD_SPARSE));
352 };
353 *yi += v * t;
354 }
355 Ok(())
356}
357
358fn gather<T: Real>(rows: &[u32], vals: &[T], x: &[T]) -> Result<T, OperatorError> {
360 let mut s = T::ZERO;
361 for (&i, &v) in rows.iter().zip(vals) {
362 let Some(&xi) = x.get(i as usize) else {
363 return Err(OperatorError::new(BAD_SPARSE));
364 };
365 s += v * xi;
366 }
367 Ok(s)
368}
369
370impl<T: Real> LinearOperator<T> for CscMatrix<T> {
373 fn nrows(&self) -> usize {
374 self.n_rows()
375 }
376 fn ncols(&self) -> usize {
377 self.n_cols()
378 }
379 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
380 check(x.len(), self.n_cols(), y.len(), self.n_rows())?;
381 y.fill(T::ZERO);
382 for (j, &xj) in x.iter().enumerate() {
383 if crate::real::is_exact_zero(xj) {
384 continue;
385 }
386 let (r, v) = segment(&self.col_ptr, &self.row_idx, &self.val, j)?;
387 scatter(r, v, xj, y)?;
388 }
389 Ok(())
390 }
391}
392impl<T: Real> AdjointOperator<T> for CscMatrix<T> {
393 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
394 check(x.len(), self.n_rows(), y.len(), self.n_cols())?;
395 for (j, yj) in y.iter_mut().enumerate() {
396 let (r, v) = segment(&self.col_ptr, &self.row_idx, &self.val, j)?;
397 *yj = gather(r, v, x)?;
398 }
399 Ok(())
400 }
401}
402impl<T: Real> LinearOperator<T> for CsrMatrix<T> {
404 fn nrows(&self) -> usize {
405 self.n_rows()
406 }
407 fn ncols(&self) -> usize {
408 self.n_cols()
409 }
410 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
411 check(x.len(), self.n_cols(), y.len(), self.n_rows())?;
412 for (i, yi) in y.iter_mut().enumerate() {
413 let (c, v) = segment(&self.row_ptr, &self.col_idx, &self.val, i)?;
414 *yi = gather(c, v, x)?;
415 }
416 Ok(())
417 }
418}
419impl<T: Real> AdjointOperator<T> for CsrMatrix<T> {
420 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
421 check(x.len(), self.n_rows(), y.len(), self.n_cols())?;
422 y.fill(T::ZERO);
423 for (i, &xi) in x.iter().enumerate() {
424 let (c, v) = segment(&self.row_ptr, &self.col_idx, &self.val, i)?;
425 scatter(c, v, xi, y)?;
426 }
427 Ok(())
428 }
429}
430
431#[derive(Debug)]
436pub struct FnOperator<F> {
437 nrows: usize,
438 ncols: usize,
439 f: F,
440}
441
442#[derive(Debug)]
445pub struct FnAdjointOperator<F, G> {
446 nrows: usize,
447 ncols: usize,
448 f: F,
449 g: G,
450}
451
452pub fn from_fn<T, F>(nrows: usize, ncols: usize, f: F) -> FnOperator<F>
454where
455 T: Real,
456 F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
457{
458 FnOperator { nrows, ncols, f }
459}
460
461pub fn from_fns<T, F, G>(nrows: usize, ncols: usize, f: F, g: G) -> FnAdjointOperator<F, G>
463where
464 T: Real,
465 F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
466 G: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
467{
468 FnAdjointOperator { nrows, ncols, f, g }
469}
470
471impl<T: Real, F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>> LinearOperator<T>
472 for FnOperator<F>
473{
474 fn nrows(&self) -> usize {
475 self.nrows
476 }
477 fn ncols(&self) -> usize {
478 self.ncols
479 }
480 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
481 (self.f)(x, y)
482 }
483}
484
485impl<T, F, G> LinearOperator<T> for FnAdjointOperator<F, G>
486where
487 T: Real,
488 F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
489{
490 fn nrows(&self) -> usize {
491 self.nrows
492 }
493 fn ncols(&self) -> usize {
494 self.ncols
495 }
496 fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
497 (self.f)(x, y)
498 }
499}
500
501impl<T, F, G> AdjointOperator<T> for FnAdjointOperator<F, G>
502where
503 T: Real,
504 F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
505 G: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
506{
507 fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
508 (self.g)(x, y)
509 }
510}
511
512#[cfg(test)]
513#[allow(clippy::float_cmp)] mod tests {
515 use super::*;
516 use xingo_sparse::{Col, Row};
517
518 fn dense() -> DenseBlock<f64> {
520 DenseBlock {
521 rows: 4,
522 cols: 3,
523 data: vec![1.0, 0.0, 4.0, 0.0, 0.0, 3.0, 0.0, 6.0, 2.0, 0.0, 5.0, 0.0],
524 }
525 }
526 fn csc() -> CscMatrix<f64> {
527 let d = dense();
528 let mut t = Vec::new();
529 for j in 0..3 {
530 for i in 0..4 {
531 if d.get(i, j) != 0.0 {
532 t.push((Row::from_usize(i), Col::from_usize(j), d.get(i, j)));
533 }
534 }
535 }
536 CscMatrix::from_triplets(4, 3, &t).unwrap()
537 }
538
539 fn check_op<O: AdjointOperator<f64>>(op: &mut O) {
540 let x = [1.0, -2.0, 0.5];
541 let mut y = [9.0; 4];
542 op.apply(&x, &mut y).unwrap();
543 assert_eq!(y, [2.0, -6.0, 6.5, -12.0]);
544 let z = [1.0, 1.0, -1.0, 2.0];
545 let mut w = [9.0; 3];
546 op.apply_t(&z, &mut w).unwrap();
547 assert_eq!(w, [-3.0, 15.0, -3.0]);
548 assert!(op.apply(&x[..2], &mut y).is_err());
549 assert!(op.apply_t(&z, &mut y).is_err());
550 let xb = [1.0, -2.0, 0.5, 0.3, 0.7, -1.1];
552 let mut yb = [0.0; 8];
553 op.apply_block(
554 MatRef::new(3, 2, 3, &xb).unwrap(),
555 MatMut::new(4, 2, 4, &mut yb).unwrap(),
556 )
557 .unwrap();
558 let mut y2 = [0.0; 4];
559 op.apply(&xb[3..], &mut y2).unwrap();
560 assert_eq!(&yb[4..], &y2);
561 let mut wb = [0.0; 6];
562 let zb = [z, [0.5, -0.25, 2.0, 1.5]].concat();
563 op.apply_t_block(
564 MatRef::new(4, 2, 4, &zb).unwrap(),
565 MatMut::new(3, 2, 3, &mut wb).unwrap(),
566 )
567 .unwrap();
568 let mut w2 = [0.0; 3];
569 op.apply_t(&zb[4..], &mut w2).unwrap();
570 assert_eq!(&wb[3..], &w2);
571 assert!(
572 op.apply_block(
573 MatRef::new(3, 2, 3, &xb).unwrap(),
574 MatMut::new(3, 2, 3, &mut wb).unwrap()
575 )
576 .is_err()
577 );
578 }
579
580 fn by_value<O: AdjointOperator<f64>>(mut o: O) {
582 check_op(&mut o);
583 }
584
585 #[test]
586 fn every_storage_applies_the_same_matrix() {
587 check_op(&mut dense());
588 check_op(&mut csc());
589 check_op(&mut csc().to_csr());
590 let d = dense();
591 let mut padded = vec![f64::NAN; 15];
593 for j in 0..3 {
594 for i in 0..4 {
595 padded[i + 5 * j] = d.get(i, j);
596 }
597 }
598 check_op(&mut MatRef::new(4, 3, 5, &padded).unwrap());
599 let (a, b) = (d.clone(), d.clone());
600 let mut f = from_fns(
601 4,
602 3,
603 move |x: &[f64], y: &mut [f64]| a.clone().apply(x, y),
604 move |x: &[f64], y: &mut [f64]| b.clone().apply_t(x, y),
605 );
606 check_op(&mut f);
607 by_value(&mut f);
609 let mut g = from_fn(1, 1, |_: &[f64], _: &mut [f64]| {
610 Err(OperatorError::new("inner solve failed"))
611 });
612 assert_eq!(
613 g.apply(&[1.0], &mut [0.0]).unwrap_err().message,
614 "inner solve failed"
615 );
616 assert_eq!((g.nrows(), g.ncols()), (1, 1));
617 }
618
619 #[test]
620 fn inconsistent_fields_are_errors_not_panics() {
621 let mut a = csc();
622 a.row_idx[0] = 99;
623 assert!(a.apply(&[1.0, 1.0, 1.0], &mut [0.0; 4]).is_err());
624 assert!(a.apply_t(&[1.0; 4], &mut [0.0; 3]).is_err());
625 let mut c = csc().to_csr();
626 c.row_ptr[1] = 1000;
627 assert!(c.apply(&[1.0; 3], &mut [0.0; 4]).is_err());
628 let mut d = dense();
629 d.data.pop();
630 assert!(d.apply(&[1.0; 3], &mut [0.0; 4]).is_err());
631 assert!(d.apply_t(&[1.0; 4], &mut [0.0; 3]).is_err());
632 }
633}