1#![no_std]
2#![forbid(unsafe_code)]
3#![allow(clippy::needless_range_loop, clippy::type_complexity)]
6extern crate alloc;
49
50use core::fmt;
51use core::ops::{Add, Div, Index, Mul, Neg, Sub};
52
53use alloc::vec::Vec;
54#[cfg(feature = "alloc")]
55use tpt_math_linalg_dense::DMatrix;
56#[cfg(feature = "alloc")]
57use tpt_math_numeric::Float;
58use tpt_math_numeric::Scalar;
59
60#[cfg(feature = "alloc")]
61use alloc::vec;
62
63#[derive(Clone, Copy, Debug, PartialEq)]
73pub struct Complex<T = f64> {
74 pub re: T,
76 pub im: T,
78}
79
80impl<T: Scalar> Complex<T> {
81 pub fn new(re: T, im: T) -> Self {
83 Complex { re, im }
84 }
85
86 pub fn from_real(re: T) -> Self {
88 Complex { re, im: T::zero() }
89 }
90
91 pub fn conj(&self) -> Self {
93 Complex {
94 re: self.re,
95 im: -self.im,
96 }
97 }
98
99 pub fn norm_sqr(&self) -> T {
101 self.re * self.re + self.im * self.im
102 }
103
104 pub fn norm(&self) -> T {
107 let (a, b) = (self.re.abs(), self.im.abs());
108 let (big, small) = if a >= b { (a, b) } else { (b, a) };
109 if big == T::zero() {
110 return T::zero();
111 }
112 let r = small / big;
113 big * (T::one() + r * r).sqrt()
114 }
115
116 pub fn arg(&self) -> T {
118 self.im.atan2(self.re)
119 }
120
121 pub fn inv(&self) -> Option<Self> {
123 if self.re == T::zero() && self.im == T::zero() {
124 return None;
125 }
126 if self.re.abs() >= self.im.abs() {
129 let r = self.im / self.re;
130 let den = self.re + self.im * r;
131 Some(Complex::new(T::one() / den, -r / den))
132 } else {
133 let r = self.re / self.im;
134 let den = self.re * r + self.im;
135 Some(Complex::new(r / den, -T::one() / den))
136 }
137 }
138
139 pub fn sqrt(&self) -> Self {
141 let r = self.norm();
143 let re = ((r + self.re) / (T::one() + T::one())).sqrt();
144 let mut im = ((r - self.re) / (T::one() + T::one())).sqrt();
145 if self.im < T::zero() {
146 im = -im;
147 }
148 Complex::new(re, im)
149 }
150}
151
152impl<T: Scalar + Copy> Complex<T> {
153 pub fn from_polar(r: T, theta: T) -> Self {
155 let (s, c) = theta.sin_cos();
156 Complex::new(r * c, r * s)
157 }
158}
159
160impl<T: Scalar + Copy> Add for Complex<T> {
161 type Output = Complex<T>;
162 fn add(self, rhs: Complex<T>) -> Complex<T> {
163 Complex::new(self.re + rhs.re, self.im + rhs.im)
164 }
165}
166
167impl<T: Scalar + Copy> Sub for Complex<T> {
168 type Output = Complex<T>;
169 fn sub(self, rhs: Complex<T>) -> Complex<T> {
170 Complex::new(self.re - rhs.re, self.im - rhs.im)
171 }
172}
173
174impl<T: Scalar + Copy> Neg for Complex<T> {
175 type Output = Complex<T>;
176 fn neg(self) -> Complex<T> {
177 Complex::new(-self.re, -self.im)
178 }
179}
180
181impl<T: Scalar + Copy> Mul for Complex<T> {
182 type Output = Complex<T>;
183 fn mul(self, rhs: Complex<T>) -> Complex<T> {
184 Complex::new(
185 self.re * rhs.re - self.im * rhs.im,
186 self.re * rhs.im + self.im * rhs.re,
187 )
188 }
189}
190
191impl<T: Scalar + Copy> Div for Complex<T> {
192 type Output = Complex<T>;
193 fn div(self, rhs: Complex<T>) -> Complex<T> {
196 if rhs.re.abs() >= rhs.im.abs() {
197 let r = rhs.im / rhs.re;
198 let den = rhs.re + rhs.im * r;
199 Complex::new((self.re + self.im * r) / den, (self.im - self.re * r) / den)
200 } else {
201 let r = rhs.re / rhs.im;
202 let den = rhs.re * r + rhs.im;
203 Complex::new((self.re * r + self.im) / den, (self.im * r - self.re) / den)
204 }
205 }
206}
207
208impl<T: Scalar + Copy> Mul<T> for Complex<T> {
209 type Output = Complex<T>;
210 fn mul(self, rhs: T) -> Complex<T> {
211 Complex::new(self.re * rhs, self.im * rhs)
212 }
213}
214
215#[derive(Clone)]
221pub struct ComplexDVector<T = f64> {
222 data: Vec<Complex<T>>,
223}
224
225#[derive(Clone)]
228pub struct ComplexDMatrix<T = f64> {
229 nrows: usize,
230 ncols: usize,
231 data: Vec<Complex<T>>,
232}
233
234#[cfg(feature = "alloc")]
239impl<T: Scalar + Copy> ComplexDVector<T> {
240 pub fn zeros(n: usize) -> Self {
242 ComplexDVector::from_fn(n, |_| Complex::from_real(T::zero()))
243 }
244
245 pub fn from_vec(data: Vec<Complex<T>>) -> Self {
247 ComplexDVector { data }
248 }
249
250 pub fn from_slice(data: &[Complex<T>]) -> Self
252 where
253 T: Clone,
254 {
255 ComplexDVector {
256 data: data.to_vec(),
257 }
258 }
259
260 pub fn from_fn(n: usize, f: impl FnMut(usize) -> Complex<T>) -> Self {
262 ComplexDVector {
263 data: (0..n).map(f).collect(),
264 }
265 }
266
267 pub fn from_real_imag(re: Vec<T>, im: Vec<T>) -> Self {
269 let n = re.len().min(im.len());
270 ComplexDVector {
271 data: (0..n).map(|i| Complex::new(re[i], im[i])).collect(),
272 }
273 }
274}
275
276#[cfg(feature = "alloc")]
277impl<T: Scalar + Copy> ComplexDMatrix<T> {
278 pub fn zeros(nrows: usize, ncols: usize) -> Self {
280 ComplexDMatrix::from_fn(nrows, ncols, |_, _| Complex::from_real(T::zero()))
281 }
282
283 pub fn from_vec(nrows: usize, ncols: usize, data: Vec<Complex<T>>) -> Self {
289 assert_eq!(
290 data.len(),
291 nrows * ncols,
292 "data length {} does not match a {nrows}x{ncols} matrix",
293 data.len()
294 );
295 ComplexDMatrix { nrows, ncols, data }
296 }
297
298 pub fn from_real_row_slice(nrows: usize, ncols: usize, data: &[T]) -> Self
303 where
304 T: Clone,
305 {
306 assert_eq!(
307 data.len(),
308 nrows * ncols,
309 "data length {} does not match a {nrows}x{ncols} matrix",
310 data.len()
311 );
312 ComplexDMatrix {
313 nrows,
314 ncols,
315 data: (0..ncols)
316 .flat_map(|j| (0..nrows).map(move |i| Complex::from_real(data[i * ncols + j])))
317 .collect(),
318 }
319 }
320
321 pub fn from_row_slice(nrows: usize, ncols: usize, data: &[Complex<T>]) -> Self
326 where
327 T: Clone,
328 {
329 assert_eq!(
330 data.len(),
331 nrows * ncols,
332 "data length {} does not match a {nrows}x{ncols} matrix",
333 data.len()
334 );
335 ComplexDMatrix {
336 nrows,
337 ncols,
338 data: (0..ncols)
339 .flat_map(|j| (0..nrows).map(move |i| data[i * ncols + j]))
340 .collect(),
341 }
342 }
343
344 pub fn from_fn(
346 nrows: usize,
347 ncols: usize,
348 mut f: impl FnMut(usize, usize) -> Complex<T>,
349 ) -> Self {
350 let mut data = Vec::with_capacity(nrows * ncols);
351 for j in 0..ncols {
352 for i in 0..nrows {
353 data.push(f(i, j));
354 }
355 }
356 ComplexDMatrix { nrows, ncols, data }
357 }
358
359 pub fn from_real_matrix(m: &DMatrix<f64>) -> ComplexDMatrix<f64> {
361 let (r, c) = (m.nrows(), m.ncols());
362 ComplexDMatrix::from_fn(r, c, |i, j| Complex::from_real(m[(i, j)]))
363 }
364}
365
366impl<T> ComplexDVector<T> {
371 pub fn len(&self) -> usize {
373 self.data.len()
374 }
375
376 pub fn is_empty(&self) -> bool {
378 self.data.is_empty()
379 }
380
381 pub fn iter(&self) -> impl Iterator<Item = &Complex<T>> {
383 self.data.iter()
384 }
385}
386
387impl<T> ComplexDMatrix<T> {
388 pub fn nrows(&self) -> usize {
390 self.nrows
391 }
392
393 pub fn ncols(&self) -> usize {
395 self.ncols
396 }
397
398 pub fn is_empty(&self) -> bool {
400 self.nrows == 0 || self.ncols == 0
401 }
402
403 pub fn iter(&self) -> impl Iterator<Item = &Complex<T>> {
405 self.data.iter()
406 }
407
408 fn offset(&self, i: usize, j: usize) -> usize {
410 i + j * self.nrows
411 }
412}
413
414impl<T> Index<usize> for ComplexDVector<T> {
415 type Output = Complex<T>;
416 fn index(&self, i: usize) -> &Complex<T> {
420 &self.data[i]
421 }
422}
423
424impl<T> Index<(usize, usize)> for ComplexDMatrix<T> {
425 type Output = Complex<T>;
426 fn index(&self, (i, j): (usize, usize)) -> &Complex<T> {
430 assert!(
432 i < self.nrows && j < self.ncols,
433 "index ({i}, {j}) out of bounds for a {}x{} matrix",
434 self.nrows,
435 self.ncols
436 );
437 &self.data[self.offset(i, j)]
438 }
439}
440
441impl<T: Scalar + Copy> ComplexDVector<T> {
446 pub fn norm(&self) -> T {
448 self.data
449 .iter()
450 .fold(T::zero(), |acc, z| acc + z.norm_sqr())
451 .sqrt()
452 }
453
454 pub fn dot(&self, other: &ComplexDVector<T>) -> Complex<T> {
456 assert_eq!(
457 self.data.len(),
458 other.data.len(),
459 "dot product requires equal lengths"
460 );
461 let mut s = Complex::from_real(T::zero());
462 for i in 0..self.data.len() {
463 s = s + self.data[i].conj() * other.data[i];
464 }
465 s
466 }
467}
468
469#[cfg(feature = "alloc")]
474impl<T: Scalar + Copy> ComplexDVector<T> {
475 pub fn transpose(&self) -> ComplexDMatrix<T> {
477 let n = self.len();
478 ComplexDMatrix::from_fn(1, n, |_, j| self[j])
479 }
480}
481
482#[cfg(feature = "alloc")]
483impl<T: Scalar + Copy> ComplexDMatrix<T> {
484 pub fn transpose(&self) -> ComplexDMatrix<T> {
486 let (m, n) = (self.nrows, self.ncols);
487 ComplexDMatrix::from_fn(n, m, |i, j| self[(j, i)])
488 }
489}
490
491#[cfg(feature = "alloc")]
492impl<T: Scalar + Copy> Add for ComplexDVector<T> {
493 type Output = ComplexDVector<T>;
494 fn add(self, rhs: ComplexDVector<T>) -> ComplexDVector<T> {
495 let n = self.len();
496 ComplexDVector::from_fn(n, |i| self[i] + rhs[i])
497 }
498}
499
500#[cfg(feature = "alloc")]
501impl<T: Scalar + Copy> Sub for ComplexDVector<T> {
502 type Output = ComplexDVector<T>;
503 fn sub(self, rhs: ComplexDVector<T>) -> ComplexDVector<T> {
504 let n = self.len();
505 ComplexDVector::from_fn(n, |i| self[i] - rhs[i])
506 }
507}
508
509#[cfg(feature = "alloc")]
510impl<T: Scalar + Copy> Neg for ComplexDVector<T> {
511 type Output = ComplexDVector<T>;
512 fn neg(self) -> ComplexDVector<T> {
513 let n = self.len();
514 ComplexDVector::from_fn(n, |i| -self[i])
515 }
516}
517
518#[cfg(feature = "alloc")]
519impl<T: Scalar + Copy> Mul<T> for ComplexDVector<T> {
520 type Output = ComplexDVector<T>;
521 fn mul(self, rhs: T) -> ComplexDVector<T> {
522 let n = self.len();
523 ComplexDVector::from_fn(n, |i| self[i] * rhs)
524 }
525}
526
527#[cfg(feature = "alloc")]
528impl<T: Scalar + Copy> Add for ComplexDMatrix<T> {
529 type Output = ComplexDMatrix<T>;
530 fn add(self, rhs: ComplexDMatrix<T>) -> ComplexDMatrix<T> {
531 let (m, n) = (self.nrows, self.ncols);
532 ComplexDMatrix::from_fn(m, n, |i, j| self[(i, j)] + rhs[(i, j)])
533 }
534}
535
536#[cfg(feature = "alloc")]
537impl<T: Scalar + Copy> Sub for ComplexDMatrix<T> {
538 type Output = ComplexDMatrix<T>;
539 fn sub(self, rhs: ComplexDMatrix<T>) -> ComplexDMatrix<T> {
540 let (m, n) = (self.nrows, self.ncols);
541 ComplexDMatrix::from_fn(m, n, |i, j| self[(i, j)] - rhs[(i, j)])
542 }
543}
544
545#[cfg(feature = "alloc")]
546impl<T: Scalar + Copy> Neg for ComplexDMatrix<T> {
547 type Output = ComplexDMatrix<T>;
548 fn neg(self) -> ComplexDMatrix<T> {
549 let (m, n) = (self.nrows, self.ncols);
550 ComplexDMatrix::from_fn(m, n, |i, j| -self[(i, j)])
551 }
552}
553
554#[cfg(feature = "alloc")]
555impl<T: Scalar + Copy> Mul<T> for ComplexDMatrix<T> {
556 type Output = ComplexDMatrix<T>;
557 fn mul(self, rhs: T) -> ComplexDMatrix<T> {
558 let (m, n) = (self.nrows, self.ncols);
559 ComplexDMatrix::from_fn(m, n, |i, j| self[(i, j)] * rhs)
560 }
561}
562
563#[cfg(feature = "alloc")]
566impl<T: Scalar + Copy> Mul<ComplexDMatrix<T>> for ComplexDMatrix<T> {
567 type Output = ComplexDMatrix<T>;
568 fn mul(self, rhs: ComplexDMatrix<T>) -> ComplexDMatrix<T> {
572 assert_eq!(
573 self.ncols, rhs.nrows,
574 "inner dimensions do not match: {}x{} * {}x{}",
575 self.nrows, self.ncols, rhs.nrows, rhs.ncols
576 );
577 let m = self.nrows;
578 let k = self.ncols;
579 let n = rhs.ncols;
580 ComplexDMatrix::from_fn(m, n, |i, j| {
581 let mut s = Complex::from_real(T::zero());
582 for kk in 0..k {
583 s = s + self[(i, kk)] * rhs[(kk, j)];
584 }
585 s
586 })
587 }
588}
589
590#[cfg(feature = "alloc")]
591impl<T: Scalar + Copy> Mul<ComplexDVector<T>> for ComplexDMatrix<T> {
592 type Output = ComplexDVector<T>;
593 fn mul(self, rhs: ComplexDVector<T>) -> ComplexDVector<T> {
597 assert_eq!(
598 self.ncols,
599 rhs.len(),
600 "matrix has {} columns but vector has length {}",
601 self.ncols,
602 rhs.len()
603 );
604 let m = self.nrows;
605 let k = self.ncols;
606 ComplexDVector::from_fn(m, |i| {
607 let mut s = Complex::from_real(T::zero());
608 for kk in 0..k {
609 s = s + self[(i, kk)] * rhs[kk];
610 }
611 s
612 })
613 }
614}
615
616impl<T: PartialEq> PartialEq for ComplexDVector<T> {
621 fn eq(&self, other: &Self) -> bool {
622 self.data == other.data
623 }
624}
625
626impl<T: PartialEq> PartialEq for ComplexDMatrix<T> {
627 fn eq(&self, other: &Self) -> bool {
628 self.nrows == other.nrows && self.ncols == other.ncols && self.data == other.data
629 }
630}
631
632#[cfg(feature = "alloc")]
633impl<T: fmt::Debug> fmt::Debug for ComplexDVector<T> {
634 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
635 f.debug_list().entries(self.iter()).finish()
636 }
637}
638
639impl<T: fmt::Debug> fmt::Debug for ComplexDMatrix<T> {
640 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
641 f.debug_struct("ComplexDMatrix")
642 .field("nrows", &self.nrows)
643 .field("ncols", &self.ncols)
644 .finish()
645 }
646}
647
648#[cfg(feature = "alloc")]
654#[derive(Debug, Clone, PartialEq)]
655#[non_exhaustive]
656pub enum ComplexDenseError {
657 Singular {
659 what: &'static str,
661 },
662 DimensionMismatch {
664 what: alloc::string::String,
666 },
667 NotConverged {
669 iterations: usize,
671 },
672}
673
674#[cfg(feature = "alloc")]
675impl fmt::Display for ComplexDenseError {
676 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
677 match self {
678 ComplexDenseError::Singular { what } => write!(f, "singular matrix in {what}"),
679 ComplexDenseError::DimensionMismatch { what } => {
680 write!(f, "dimension mismatch: {what}")
681 }
682 ComplexDenseError::NotConverged { iterations } => {
683 write!(f, "did not converge after {iterations} iterations")
684 }
685 }
686 }
687}
688
689#[cfg(feature = "alloc")]
690impl core::error::Error for ComplexDenseError {}
691
692#[cfg(feature = "alloc")]
693impl ComplexDMatrix<f64> {
694 pub fn lu_with_relative_tolerance(
702 &self,
703 rel: f64,
704 ) -> Result<(Vec<Vec<Complex<f64>>>, Vec<Vec<Complex<f64>>>, Vec<usize>), ComplexDenseError>
705 {
706 let scale = self.iter().fold(0.0_f64, |acc, z| acc.max(z.norm()));
707 self.lu_with_tolerance(rel * scale)
708 }
709
710 pub fn lu(
715 &self,
716 ) -> Result<(Vec<Vec<Complex<f64>>>, Vec<Vec<Complex<f64>>>, Vec<usize>), ComplexDenseError>
717 {
718 self.lu_with_tolerance(1e-12)
719 }
720
721 pub fn lu_with_tolerance(
729 &self,
730 tol: f64,
731 ) -> Result<(Vec<Vec<Complex<f64>>>, Vec<Vec<Complex<f64>>>, Vec<usize>), ComplexDenseError>
732 {
733 let n = self.nrows;
734 if self.ncols != n {
735 return Err(ComplexDenseError::DimensionMismatch {
736 what: alloc::format!("matrix is {}x{}, expected square", n, self.ncols),
737 });
738 }
739 #[cfg(feature = "simd-runtime")]
740 {
741 if n >= simd_lu::CUTOFF {
742 let factors = simd_lu::factor(self, tol)?;
743 return Ok(simd_lu::to_lu(&factors));
744 }
745 }
746 let mut a: Vec<Vec<Complex<f64>>> = (0..n)
747 .map(|i| (0..n).map(|j| self[(i, j)]).collect())
748 .collect();
749 let mut piv: Vec<usize> = (0..n).collect();
750
751 for k in 0..n {
752 let mut p = k;
753 let mut max = a[k][k].norm();
754 for i in (k + 1)..n {
755 let v = a[i][k].norm();
756 if v > max {
757 max = v;
758 p = i;
759 }
760 }
761 if !max.is_finite() || max == 0.0 || max < tol {
762 return Err(ComplexDenseError::Singular { what: "lu" });
763 }
764 a.swap(k, p);
765 piv.swap(k, p);
766 for i in (k + 1)..n {
767 a[i][k] = a[i][k] / a[k][k];
768 for j in (k + 1)..n {
769 a[i][j] = a[i][j] - a[i][k] * a[k][j];
770 }
771 }
772 }
773 let l: Vec<Vec<Complex<f64>>> = (0..n)
774 .map(|i| {
775 (0..n)
776 .map(|j| {
777 if i == j {
778 Complex::from_real(1.0)
779 } else if i > j {
780 a[i][j]
781 } else {
782 Complex::from_real(0.0)
783 }
784 })
785 .collect()
786 })
787 .collect();
788 let u: Vec<Vec<Complex<f64>>> = (0..n)
789 .map(|i| {
790 (0..n)
791 .map(|j| {
792 if i <= j {
793 a[i][j]
794 } else {
795 Complex::from_real(0.0)
796 }
797 })
798 .collect()
799 })
800 .collect();
801 Ok((l, u, piv))
802 }
803
804 pub fn solve(&self, b: &ComplexDVector<f64>) -> Result<ComplexDVector<f64>, ComplexDenseError> {
806 let n = self.nrows;
807 if self.ncols != n {
808 return Err(ComplexDenseError::DimensionMismatch {
809 what: alloc::format!("matrix is {}x{}, expected square", n, self.ncols),
810 });
811 }
812 if b.len() != n {
813 return Err(ComplexDenseError::DimensionMismatch {
814 what: alloc::format!("rhs has length {}, expected {n}", b.len()),
815 });
816 }
817 #[cfg(feature = "simd-runtime")]
818 {
819 if n >= simd_lu::CUTOFF {
820 let factors = simd_lu::factor(self, 1e-12)?;
821 let rhs = ComplexDMatrix::from_fn(n, 1, |i, _| b[i]);
822 let x = simd_lu::solve(&factors, &rhs);
823 return Ok(ComplexDVector::from_fn(n, |i| x[(i, 0)]));
824 }
825 }
826 let (l, u, piv) = self.lu()?;
827 let x = solve_with_lu(&l, &u, &piv, b);
828 Ok(ComplexDVector::from_vec(x))
829 }
830
831 pub fn inverse(&self) -> Result<ComplexDMatrix<f64>, ComplexDenseError> {
833 let n = self.nrows;
834 if self.ncols != n {
835 return Err(ComplexDenseError::DimensionMismatch {
836 what: alloc::format!("matrix is {}x{}, expected square", n, self.ncols),
837 });
838 }
839 #[cfg(feature = "simd-runtime")]
840 {
841 if n >= simd_lu::CUTOFF {
842 let factors = simd_lu::factor(self, 1e-12)?;
843 let identity = ComplexDMatrix::from_fn(n, n, |i, j| {
844 Complex::from_real(if i == j { 1.0 } else { 0.0 })
845 });
846 return Ok(simd_lu::solve(&factors, &identity));
847 }
848 }
849 let (l, u, piv) = self.lu()?;
850 let mut out = Vec::with_capacity(n * n);
851 for col in 0..n {
852 let mut e = vec![Complex::from_real(0.0_f64); n];
853 e[col] = Complex::from_real(1.0);
854 let x = solve_with_lu(&l, &u, &piv, &ComplexDVector::from_vec(e));
855 out.extend(x);
856 }
857 Ok(ComplexDMatrix::from_vec(n, n, out))
858 }
859
860 pub fn cholesky(&self) -> Result<Cholesky<f64>, ComplexDenseError> {
863 let n = self.nrows;
864 if self.ncols != n {
865 return Err(ComplexDenseError::DimensionMismatch {
866 what: alloc::format!("matrix is {}x{}, expected square", n, self.ncols),
867 });
868 }
869 let mut l: Vec<Vec<Complex<f64>>> = vec![vec![Complex::from_real(0.0); n]; n];
870 for j in 0..n {
871 let mut d = self[(j, j)];
873 for k in 0..j {
874 d = d - l[j][k] * l[j][k].conj();
875 }
876 if d.re <= 0.0 || !d.re.is_finite() {
877 return Err(ComplexDenseError::Singular { what: "cholesky" });
878 }
879 let ljj = d.sqrt();
880 l[j][j] = ljj;
881 for i in (j + 1)..n {
882 let mut s = self[(i, j)];
883 for k in 0..j {
884 s = s - l[i][k] * l[j][k].conj();
885 }
886 l[i][j] = s / ljj;
887 }
888 }
889 Ok(Cholesky { l, n })
890 }
891
892 pub fn eigenvalues(&self) -> Vec<Complex<f64>> {
902 self.try_eigenvalues()
903 .unwrap_or_else(|e| panic!("eigenvalues failed: {e}"))
904 }
905
906 pub fn try_eigenvalues(&self) -> Result<Vec<Complex<f64>>, ComplexDenseError> {
914 hessenberg_qr_eigenvalues(self)
915 }
916}
917
918#[cfg(feature = "alloc")]
919fn solve_with_lu(
920 l: &[Vec<Complex<f64>>],
921 u: &[Vec<Complex<f64>>],
922 piv: &[usize],
923 b: &ComplexDVector<f64>,
924) -> Vec<Complex<f64>> {
925 let n = l.len();
926 let mut y = vec![Complex::from_real(0.0_f64); n];
928 for i in 0..n {
929 let mut s = b[piv[i]];
930 for j in 0..i {
931 s = s - l[i][j] * y[j];
932 }
933 y[i] = s;
934 }
935 let mut x = vec![Complex::from_real(0.0_f64); n];
937 for i in (0..n).rev() {
938 let mut s = y[i];
939 for j in (i + 1)..n {
940 s = s - u[i][j] * x[j];
941 }
942 x[i] = s / u[i][i];
943 }
944 x
945}
946
947#[cfg(feature = "alloc")]
954#[derive(Clone, Debug)]
955pub struct Cholesky<T = f64> {
956 l: Vec<Vec<Complex<T>>>,
957 n: usize,
958}
959
960#[cfg(feature = "alloc")]
961impl Cholesky<f64> {
962 pub fn solve(&self, b: &ComplexDVector<f64>) -> Result<ComplexDVector<f64>, ComplexDenseError> {
964 let n = self.n;
965 if b.len() != n {
966 return Err(ComplexDenseError::DimensionMismatch {
967 what: alloc::format!("rhs has length {}, expected {n}", b.len()),
968 });
969 }
970 let mut y = vec![Complex::from_real(0.0_f64); n];
972 for i in 0..n {
973 let mut s = b[i];
974 for j in 0..i {
975 s = s - self.l[i][j] * y[j];
976 }
977 y[i] = s / self.l[i][i];
978 }
979 let mut x = vec![Complex::from_real(0.0_f64); n];
981 for i in (0..n).rev() {
982 let mut s = y[i];
983 for j in (i + 1)..n {
984 s = s - self.l[j][i].conj() * x[j];
985 }
986 x[i] = s / self.l[i][i].conj();
987 }
988 Ok(ComplexDVector::from_vec(x))
989 }
990}
991
992#[cfg(feature = "alloc")]
1004fn hessenberg_qr_eigenvalues(
1005 m: &ComplexDMatrix<f64>,
1006) -> Result<Vec<Complex<f64>>, ComplexDenseError> {
1007 let n = m.nrows;
1008 if m.ncols != n {
1009 return Err(ComplexDenseError::DimensionMismatch {
1010 what: alloc::format!(
1011 "eigenvalues need a square matrix, got {}x{}",
1012 m.nrows,
1013 m.ncols
1014 ),
1015 });
1016 }
1017 if n == 0 {
1018 return Ok(Vec::new());
1019 }
1020 let mut a: Vec<Vec<Complex<f64>>> = (0..n)
1021 .map(|i| (0..n).map(|j| m[(i, j)]).collect())
1022 .collect();
1023 hessenberg_reduce(&mut a);
1024
1025 let zero = Complex::from_real(0.0_f64);
1026 let mut eig = vec![zero; n];
1027 let max_total = 50 * n.max(1);
1029 let mut total = 0_usize;
1030 let mut since_deflation = 0_usize;
1031 let mut hi = n - 1;
1032
1033 while hi > 0 {
1034 let mut lo = hi;
1037 while lo > 0 {
1038 let sub = a[lo][lo - 1].norm();
1039 let scale = a[lo - 1][lo - 1].norm() + a[lo][lo].norm();
1040 if sub <= f64::EPSILON * scale {
1041 a[lo][lo - 1] = zero;
1042 break;
1043 }
1044 lo -= 1;
1045 }
1046 if lo == hi {
1047 eig[hi] = a[hi][hi];
1048 hi -= 1;
1049 since_deflation = 0;
1050 continue;
1051 }
1052
1053 if total >= max_total {
1054 return Err(ComplexDenseError::NotConverged { iterations: total });
1055 }
1056 total += 1;
1057 since_deflation += 1;
1058 let mu = if since_deflation % 11 == 0 {
1059 a[hi][hi] + Complex::from_real(0.75 * a[hi][hi - 1].norm())
1061 } else {
1062 wilkinson_shift(a[hi - 1][hi - 1], a[hi - 1][hi], a[hi][hi - 1], a[hi][hi])
1063 };
1064 qr_sweep(&mut a, lo, hi, mu);
1065 }
1066 eig[0] = a[0][0];
1067 Ok(eig)
1068}
1069
1070#[cfg(feature = "alloc")]
1072fn hessenberg_reduce(a: &mut [Vec<Complex<f64>>]) {
1073 let n = a.len();
1074 let zero = Complex::from_real(0.0_f64);
1075 for k in 0..n.saturating_sub(2) {
1076 let len = n - k - 1;
1077 let x: Vec<Complex<f64>> = (0..len).map(|i| a[k + 1 + i][k]).collect();
1078 let nx = Float::sqrt(x.iter().fold(0.0_f64, |acc, z| acc + z.norm_sqr()));
1079 if nx == 0.0 {
1080 continue;
1081 }
1082 let x0_mod = x[0].norm();
1084 let phase = if x0_mod == 0.0 {
1085 Complex::from_real(1.0_f64)
1086 } else {
1087 x[0] * (1.0 / x0_mod)
1088 };
1089 let alpha = -(phase * Complex::from_real(nx));
1090 let mut v = x;
1091 v[0] = v[0] - alpha;
1092 let nv = Float::sqrt(v.iter().fold(0.0_f64, |acc, z| acc + z.norm_sqr()));
1093 if nv == 0.0 {
1094 continue;
1095 }
1096 let u: Vec<Complex<f64>> = v.iter().map(|z| *z * (1.0 / nv)).collect();
1097
1098 for j in 0..n {
1101 let mut s = zero;
1102 for (i, ui) in u.iter().enumerate() {
1103 s = s + ui.conj() * a[k + 1 + i][j];
1104 }
1105 let s2 = s * 2.0;
1106 for (i, ui) in u.iter().enumerate() {
1107 a[k + 1 + i][j] = a[k + 1 + i][j] - *ui * s2;
1108 }
1109 }
1110 for row in a.iter_mut() {
1111 let mut s = zero;
1112 for (jj, uj) in u.iter().enumerate() {
1113 s = s + row[k + 1 + jj] * *uj;
1114 }
1115 let s2 = s * 2.0;
1116 for (jj, uj) in u.iter().enumerate() {
1117 row[k + 1 + jj] = row[k + 1 + jj] - s2 * uj.conj();
1118 }
1119 }
1120 }
1121}
1122
1123#[cfg(feature = "alloc")]
1125fn wilkinson_shift(
1126 a: Complex<f64>,
1127 b: Complex<f64>,
1128 c: Complex<f64>,
1129 d: Complex<f64>,
1130) -> Complex<f64> {
1131 let half = Complex::from_real(0.5_f64);
1132 let mean = (a + d) * half;
1133 let half_diff = (a - d) * half;
1134 let disc = (half_diff * half_diff + b * c).sqrt();
1135 let l1 = mean + disc;
1136 let l2 = mean - disc;
1137 if (l1 - d).norm() < (l2 - d).norm() {
1138 l1
1139 } else {
1140 l2
1141 }
1142}
1143
1144#[cfg(feature = "alloc")]
1147fn givens(x: Complex<f64>, y: Complex<f64>) -> (f64, Complex<f64>) {
1148 let nx = x.norm();
1149 let r = Float::sqrt(x.norm_sqr() + y.norm_sqr());
1150 if r == 0.0 {
1151 return (1.0, Complex::from_real(0.0));
1152 }
1153 if nx == 0.0 {
1154 return (0.0, Complex::from_real(1.0));
1155 }
1156 let c = nx / r;
1157 let s = (x * (1.0 / nx)) * y.conj() * (1.0 / r);
1158 (c, s)
1159}
1160
1161#[cfg(feature = "alloc")]
1166fn qr_sweep(a: &mut [Vec<Complex<f64>>], lo: usize, hi: usize, mu: Complex<f64>) {
1167 let n = a.len();
1168 let mut x = a[lo][lo] - mu;
1169 let mut y = a[lo + 1][lo];
1170 for k in lo..hi {
1171 let (c, s) = givens(x, y);
1172 for j in 0..n {
1174 let p = a[k][j];
1175 let q = a[k + 1][j];
1176 a[k][j] = p * c + s * q;
1177 a[k + 1][j] = -(s.conj() * p) + q * c;
1178 }
1179 for row in a.iter_mut() {
1181 let p = row[k];
1182 let q = row[k + 1];
1183 row[k] = p * c + s.conj() * q;
1184 row[k + 1] = -(s * p) + q * c;
1185 }
1186 if k + 2 <= hi {
1187 x = a[k + 1][k];
1189 y = a[k + 2][k];
1190 }
1191 }
1192}
1193
1194#[cfg(all(test, feature = "alloc"))]
1199mod tests {
1200 use super::*;
1201 use approx::assert_relative_eq;
1202
1203 type C = Complex<f64>;
1204
1205 fn c(re: f64, im: f64) -> C {
1206 Complex::new(re, im)
1207 }
1208
1209 #[test]
1210 fn complex_arithmetic() {
1211 let z = c(1.0, 2.0);
1212 assert_eq!(z * z, c(-3.0, 4.0));
1213 assert_eq!(z + c(1.0, 0.0), c(2.0, 2.0));
1214 assert_eq!(-z, c(-1.0, -2.0));
1215 assert_eq!(z.conj(), c(1.0, -2.0));
1216 assert!((z.norm() - 5.0_f64.sqrt()).abs() < 1e-12);
1217 let inv = z.inv().unwrap();
1218 assert_relative_eq!((z * inv).re, 1.0, epsilon = 1e-12);
1219 assert_relative_eq!((z * inv).im, 0.0, epsilon = 1e-12);
1220 }
1221
1222 #[test]
1223 fn division_and_norm_survive_large_magnitudes() {
1224 let big = c(1e200, 1e200);
1226 let q = big / big;
1227 assert_relative_eq!(q.re, 1.0, epsilon = 1e-12);
1228 assert_relative_eq!(q.im, 0.0, epsilon = 1e-12);
1229 assert_relative_eq!(big.norm(), 1e200 * 2.0_f64.sqrt(), max_relative = 1e-12);
1230 let inv = big.inv().unwrap();
1231 assert!(inv.re.is_finite() && inv.im.is_finite());
1232 assert_relative_eq!(inv.re, 0.5e-200, max_relative = 1e-12);
1233 }
1234
1235 #[test]
1236 fn complex_sqrt() {
1237 let r = c(-1.0, 0.0).sqrt();
1239 assert!((r.re).abs() < 1e-12);
1240 assert!((r.im - 1.0).abs() < 1e-12 || (r.im + 1.0).abs() < 1e-12);
1241 let r2 = c(0.0, 1.0).sqrt();
1243 assert_relative_eq!(r2.re, 2.0_f64.sqrt() / 2.0, epsilon = 1e-12);
1244 assert_relative_eq!(r2.im, 2.0_f64.sqrt() / 2.0, epsilon = 1e-12);
1245 }
1246
1247 #[test]
1248 fn vector_construction_index_norm_dot() {
1249 let v = ComplexDVector::from_fn(3, |i| c(i as f64, (i + 1) as f64));
1250 assert_eq!(v.len(), 3);
1251 assert_eq!(v[0], c(0.0, 1.0));
1252 let n = v.norm();
1253 assert!((n - 19.0_f64.sqrt()).abs() < 1e-12);
1255 let d = v.dot(&v);
1256 assert_relative_eq!(d.re, 19.0, epsilon = 1e-12);
1257 assert_relative_eq!(d.im, 0.0, epsilon = 1e-12);
1258 }
1259
1260 #[test]
1261 fn matrix_arithmetic_and_mul() {
1262 let m = ComplexDMatrix::from_real_row_slice(2, 2, &[1.0, 2.0, 3.0, 4.0]);
1263 let z = ComplexDMatrix::zeros(2, 2);
1264 assert_eq!(m.clone() - m.clone(), z);
1265 let v = ComplexDVector::from_vec(vec![c(1.0, 0.0), c(1.0, 0.0)]);
1266 let mv = m.clone() * v;
1267 assert_eq!(mv[0], c(3.0, 0.0));
1268 assert_eq!(mv[1], c(7.0, 0.0));
1269 let t = m.transpose();
1270 assert_eq!(t[(0, 1)], c(3.0, 0.0));
1271 }
1272
1273 #[test]
1274 fn lu_solve_inverse_real() {
1275 let a = ComplexDMatrix::from_real_row_slice(2, 2, &[2.0, 0.0, 0.0, 2.0]);
1276 let inv = a.inverse().unwrap();
1277 assert_relative_eq!(inv[(0, 0)].re, 0.5, epsilon = 1e-12);
1278 assert_relative_eq!(inv[(1, 1)].re, 0.5, epsilon = 1e-12);
1279 let b = ComplexDVector::from_vec(vec![c(4.0, 0.0), c(6.0, 0.0)]);
1280 let x = a.solve(&b).unwrap();
1281 assert_eq!(x[0], c(2.0, 0.0));
1282 assert_eq!(x[1], c(3.0, 0.0));
1283 }
1284
1285 #[test]
1286 fn lu_solve_complex() {
1287 let a = ComplexDMatrix::from_row_slice(
1289 2,
1290 2,
1291 &[c(1.0, 1.0), c(1.0, 0.0), c(0.0, 0.0), c(2.0, -1.0)],
1292 );
1293 let b = ComplexDVector::from_vec(vec![c(2.0, 1.0), c(2.0, 0.0)]);
1294 let x = a.solve(&b).unwrap();
1295 assert_relative_eq!(x[1].re, 0.8, epsilon = 1e-12);
1297 assert_relative_eq!(x[1].im, 0.4, epsilon = 1e-12);
1298 let ax = a.clone() * x;
1300 assert_relative_eq!(ax[0].re, b[0].re, epsilon = 1e-12);
1301 assert_relative_eq!(ax[0].im, b[0].im, epsilon = 1e-12);
1302 assert_relative_eq!(ax[1].re, b[1].re, epsilon = 1e-12);
1303 assert_relative_eq!(ax[1].im, b[1].im, epsilon = 1e-12);
1304 }
1305
1306 #[test]
1307 fn singular_matrix_rejected() {
1308 let a = ComplexDMatrix::from_real_row_slice(2, 2, &[1.0, 1.0, 1.0, 1.0]);
1309 assert!(a.inverse().is_err());
1310 assert!(a
1311 .solve(&ComplexDVector::from_vec(vec![c(1.0, 0.0), c(1.0, 0.0)]))
1312 .is_err());
1313 }
1314
1315 #[test]
1316 fn cholesky_hermitian_pd() {
1317 let a = ComplexDMatrix::from_row_slice(
1319 2,
1320 2,
1321 &[c(4.0, 0.0), c(1.0, -1.0), c(1.0, 1.0), c(3.0, 0.0)],
1322 );
1323 let chol = a.cholesky().unwrap();
1324 let l = ComplexDMatrix::from_vec(2, 2, {
1326 let mut v = Vec::new();
1327 for j in 0..2 {
1328 for i in 0..2 {
1329 v.push(chol.l[i][j]);
1330 }
1331 }
1332 v
1333 });
1334 let recon = mul_mm_public(&l, &ComplexDMatrix::from_fn(2, 2, |i, j| l[(j, i)].conj()));
1335 for i in 0..2 {
1336 for j in 0..2 {
1337 assert_relative_eq!(recon[(i, j)].re, a[(i, j)].re, epsilon = 1e-11);
1338 assert_relative_eq!(recon[(i, j)].im, a[(i, j)].im, epsilon = 1e-11);
1339 }
1340 }
1341 let b = ComplexDVector::from_vec(vec![c(1.0, 0.0), c(0.0, 0.0)]);
1343 let x = chol.solve(&b).unwrap();
1344 let ax = a.clone() * x;
1345 assert_relative_eq!(ax[0].re, 1.0, epsilon = 1e-11);
1346 assert_relative_eq!(ax[1].re, 0.0, epsilon = 1e-11);
1347 }
1348
1349 #[test]
1350 fn eigenvalues_diagonal() {
1351 let a = ComplexDMatrix::from_row_slice(
1353 2,
1354 2,
1355 &[c(2.0, 0.0), c(0.0, 0.0), c(0.0, 0.0), c(0.0, 3.0)],
1356 );
1357 let ev = a.eigenvalues();
1358 assert_eq!(ev.len(), 2);
1359 assert!(find(&ev, 2.0, 0.0));
1360 assert!(find(&ev, 0.0, 3.0));
1361 }
1362
1363 #[test]
1364 fn eigenvalues_rotation_like() {
1365 let a = ComplexDMatrix::from_real_row_slice(2, 2, &[0.0, -1.0, 1.0, 0.0]);
1367 let ev = a.eigenvalues();
1368 assert_eq!(ev.len(), 2);
1369 assert!(find(&ev, 0.0, -1.0));
1370 assert!(find(&ev, 0.0, 1.0));
1371 }
1372
1373 #[test]
1374 fn eigenvalues_hermitian_real_spectrum() {
1375 let a = ComplexDMatrix::from_row_slice(
1377 2,
1378 2,
1379 &[c(2.0, 0.0), c(1.0, 1.0), c(1.0, -1.0), c(2.0, 0.0)],
1380 );
1381 let ev = a.eigenvalues();
1382 assert_eq!(ev.len(), 2);
1383 let s = 2.0_f64.sqrt();
1384 assert!(find(&ev, 2.0 - s, 0.0));
1385 assert!(find(&ev, 2.0 + s, 0.0));
1386 }
1387
1388 #[test]
1389 fn eigenvalues_3x3_companion_real_roots() {
1390 let a = ComplexDMatrix::from_real_row_slice(
1392 3,
1393 3,
1394 &[0.0, 0.0, 6.0, 1.0, 0.0, -11.0, 0.0, 1.0, 6.0],
1395 );
1396 let ev = a.eigenvalues();
1397 assert_eq!(ev.len(), 3);
1398 assert!(find(&ev, 1.0, 0.0));
1399 assert!(find(&ev, 2.0, 0.0));
1400 assert!(find(&ev, 3.0, 0.0));
1401 }
1402
1403 #[test]
1404 fn eigenvalues_3x3_complex_roots() {
1405 let a = ComplexDMatrix::from_real_row_slice(
1407 3,
1408 3,
1409 &[0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0],
1410 );
1411 let ev = a.eigenvalues();
1412 let h = 0.5_f64;
1413 let s = 3.0_f64.sqrt() / 2.0;
1414 assert!(find(&ev, 1.0, 0.0));
1415 assert!(find(&ev, -h, s));
1416 assert!(find(&ev, -h, -s));
1417 }
1418
1419 #[test]
1420 fn eigenvalues_hermitian_3x3_with_repeated_value() {
1421 let a = ComplexDMatrix::from_row_slice(
1423 3,
1424 3,
1425 &[
1426 c(1.0, 0.0),
1427 c(0.0, 1.0),
1428 c(0.0, 0.0),
1429 c(0.0, -1.0),
1430 c(1.0, 0.0),
1431 c(0.0, 0.0),
1432 c(0.0, 0.0),
1433 c(0.0, 0.0),
1434 c(2.0, 0.0),
1435 ],
1436 );
1437 let ev = a.eigenvalues();
1438 assert_eq!(ev.len(), 3);
1439 assert!(find(&ev, 0.0, 0.0));
1440 assert_eq!(ev.iter().filter(|z| find(&[**z], 2.0, 0.0)).count(), 2);
1441 }
1442
1443 #[test]
1444 fn eigenvalues_4x4_trace_and_spectrum_of_triangular() {
1445 let a = ComplexDMatrix::from_row_slice(
1447 4,
1448 4,
1449 &[
1450 c(1.0, 0.0),
1451 c(5.0, 2.0),
1452 c(-3.0, 1.0),
1453 c(0.5, 0.0),
1454 c(0.0, 0.0),
1455 c(0.0, 2.0),
1456 c(4.0, 0.0),
1457 c(1.0, -1.0),
1458 c(0.0, 0.0),
1459 c(0.0, 0.0),
1460 c(-2.0, 0.0),
1461 c(2.0, 2.0),
1462 c(0.0, 0.0),
1463 c(0.0, 0.0),
1464 c(0.0, 0.0),
1465 c(0.0, -3.0),
1466 ],
1467 );
1468 let ev = a.eigenvalues();
1469 assert_eq!(ev.len(), 4);
1470 for (want_re, want_im) in [(1.0, 0.0), (0.0, 2.0), (-2.0, 0.0), (0.0, -3.0)] {
1471 assert!(find(&ev, want_re, want_im), "missing {want_re}+{want_im}i");
1472 }
1473 let trace = ev.iter().fold(C::from_real(0.0), |acc, z| acc + *z);
1474 assert_relative_eq!(trace.re, -1.0, epsilon = 1e-9);
1475 assert_relative_eq!(trace.im, -1.0, epsilon = 1e-9);
1476 }
1477
1478 #[test]
1479 fn try_eigenvalues_rejects_non_square() {
1480 let a = ComplexDMatrix::<f64>::zeros(2, 3);
1481 assert!(matches!(
1482 a.try_eigenvalues(),
1483 Err(ComplexDenseError::DimensionMismatch { .. })
1484 ));
1485 }
1486
1487 #[test]
1488 #[should_panic(expected = "length")]
1489 fn from_vec_length_mismatch_panics() {
1490 let _ = ComplexDMatrix::from_vec(2, 2, vec![c(1.0, 0.0); 3]);
1491 }
1492
1493 #[test]
1494 #[should_panic(expected = "out of bounds")]
1495 fn index_row_out_of_bounds_panics() {
1496 let m = ComplexDMatrix::<f64>::zeros(2, 3);
1498 let _ = m[(2, 0)];
1499 }
1500
1501 fn mul_mm_public(a: &ComplexDMatrix<f64>, b: &ComplexDMatrix<f64>) -> ComplexDMatrix<f64> {
1502 a.clone() * b.clone()
1503 }
1504
1505 fn find(ev: &[Complex<f64>], target_re: f64, target_im: f64) -> bool {
1506 ev.iter()
1507 .any(|z| (z.re - target_re).abs() < 1e-9 && (z.im - target_im).abs() < 1e-9)
1508 }
1509}
1510
1511#[cfg(test)]
1512mod lu_threshold_tests {
1513 use super::*;
1514
1515 #[test]
1516 fn relative_threshold_is_scale_invariant() {
1517 let a = ComplexDMatrix::from_real_row_slice(2, 2, &[4.0_f64, 1.0, 2.0, 3.0]);
1518 let tiny = ComplexDMatrix::from_real_row_slice(2, 2, &[4e-14, 1e-14, 2e-14, 3e-14]);
1519 assert!(a.lu_with_relative_tolerance(1e-10).is_ok());
1520 assert!(tiny.lu_with_relative_tolerance(1e-10).is_ok());
1521 assert!(tiny.lu().is_err());
1523 }
1524
1525 #[test]
1526 fn zero_matrix_is_singular_for_any_threshold() {
1527 let zero = ComplexDMatrix::<f64>::zeros(2, 2);
1528 assert!(zero.lu_with_tolerance(0.0).is_err());
1529 assert!(zero.lu_with_relative_tolerance(1e-10).is_err());
1530 }
1531}
1532
1533#[cfg(feature = "alloc")]
1534impl ComplexDMatrix<f64> {
1535 pub fn det(&self) -> Result<Complex<f64>, ComplexDenseError> {
1545 if self.nrows != self.ncols {
1546 return Err(ComplexDenseError::DimensionMismatch {
1547 what: alloc::format!("matrix is {}x{}, expected square", self.nrows, self.ncols),
1548 });
1549 }
1550 let (_, u, piv) = match self.lu() {
1551 Ok(factors) => factors,
1552 Err(ComplexDenseError::Singular { .. }) => {
1553 return Ok(Complex::from_real(0.0));
1554 }
1555 Err(e) => return Err(e),
1556 };
1557 let n = piv.len();
1559 let mut seen = alloc::vec![false; n];
1560 let mut cycles = 0usize;
1561 for start in 0..n {
1562 if !seen[start] {
1563 cycles += 1;
1564 let mut j = start;
1565 while !seen[j] {
1566 seen[j] = true;
1567 j = piv[j];
1568 }
1569 }
1570 }
1571 let sign = if (n - cycles) % 2 == 0 { 1.0 } else { -1.0 };
1572 let mut det = Complex::from_real(sign);
1573 for (i, row) in u.iter().enumerate() {
1574 det = det * row[i];
1575 }
1576 Ok(det)
1577 }
1578
1579 pub fn product(&self, rhs: &ComplexDMatrix<f64>) -> ComplexDMatrix<f64> {
1590 assert_eq!(
1591 self.ncols, rhs.nrows,
1592 "inner dimensions do not match: {}x{} * {}x{}",
1593 self.nrows, self.ncols, rhs.nrows, rhs.ncols
1594 );
1595 #[cfg(feature = "simd-runtime")]
1596 {
1597 if self.nrows >= simd_lu::CUTOFF && self.ncols >= simd_lu::CUTOFF {
1598 return simd_lu::gemm(self, rhs);
1599 }
1600 }
1601 self.clone() * rhs.clone()
1602 }
1603}
1604
1605#[cfg(feature = "simd-runtime")]
1611mod simd_lu {
1612 use super::*;
1613
1614 pub(super) const CUTOFF: usize = 64;
1616
1617 pub(super) struct Factors {
1619 n: usize,
1620 ar: Vec<f64>,
1621 ai: Vec<f64>,
1622 ipiv: Vec<usize>,
1623 }
1624
1625 pub(super) fn factor(m: &ComplexDMatrix<f64>, tol: f64) -> Result<Factors, ComplexDenseError> {
1627 let n = m.nrows;
1628 let mut ar = vec![0.0_f64; n * n];
1629 let mut ai = vec![0.0_f64; n * n];
1630 for j in 0..n {
1631 for i in 0..n {
1632 let z = m[(i, j)];
1633 ar[i + j * n] = z.re;
1634 ai[i + j * n] = z.im;
1635 }
1636 }
1637 let mut ipiv = vec![0usize; n];
1638 let singular = ComplexDenseError::Singular { what: "lu" };
1639 if tpt_simd_blas::getrf_c64(n, &mut ar, &mut ai, n, &mut ipiv).is_err() {
1640 return Err(singular);
1641 }
1642 for k in 0..n {
1644 let (re, im) = (ar[k + k * n], ai[k + k * n]);
1645 let modulus = re.hypot(im);
1646 if !modulus.is_finite() || modulus == 0.0 || modulus < tol {
1647 return Err(singular);
1648 }
1649 }
1650 Ok(Factors { n, ar, ai, ipiv })
1651 }
1652
1653 pub(super) fn to_lu(
1655 f: &Factors,
1656 ) -> (Vec<Vec<Complex<f64>>>, Vec<Vec<Complex<f64>>>, Vec<usize>) {
1657 let n = f.n;
1658 let at = |i: usize, j: usize| Complex::new(f.ar[i + j * n], f.ai[i + j * n]);
1659 let mut piv: Vec<usize> = (0..n).collect();
1660 for (k, &p) in f.ipiv.iter().enumerate() {
1661 piv.swap(k, p);
1662 }
1663 let zero = Complex::from_real(0.0);
1664 let one = Complex::from_real(1.0);
1665 let l = (0..n)
1666 .map(|i| {
1667 (0..n)
1668 .map(|j| match i.cmp(&j) {
1669 core::cmp::Ordering::Equal => one,
1670 core::cmp::Ordering::Greater => at(i, j),
1671 core::cmp::Ordering::Less => zero,
1672 })
1673 .collect()
1674 })
1675 .collect();
1676 let u = (0..n)
1677 .map(|i| {
1678 (0..n)
1679 .map(|j| if i <= j { at(i, j) } else { zero })
1680 .collect()
1681 })
1682 .collect();
1683 (l, u, piv)
1684 }
1685
1686 pub(super) fn gemm(a: &ComplexDMatrix<f64>, b: &ComplexDMatrix<f64>) -> ComplexDMatrix<f64> {
1688 let (m, k, n) = (a.nrows, a.ncols, b.ncols);
1689 let mut ar = vec![0.0_f64; m * k];
1690 let mut ai = vec![0.0_f64; m * k];
1691 for j in 0..k {
1692 for i in 0..m {
1693 ar[i + j * m] = a[(i, j)].re;
1694 ai[i + j * m] = a[(i, j)].im;
1695 }
1696 }
1697 let mut br = vec![0.0_f64; k * n];
1698 let mut bi = vec![0.0_f64; k * n];
1699 for j in 0..n {
1700 for i in 0..k {
1701 br[i + j * k] = b[(i, j)].re;
1702 bi[i + j * k] = b[(i, j)].im;
1703 }
1704 }
1705 let mut cr = vec![0.0_f64; m * n];
1706 let mut ci = vec![0.0_f64; m * n];
1707 tpt_simd_blas::gemm_c64(
1708 m,
1709 n,
1710 k,
1711 [1.0, 0.0],
1712 &ar,
1713 &ai,
1714 m,
1715 &br,
1716 &bi,
1717 k,
1718 [0.0, 0.0],
1719 &mut cr,
1720 &mut ci,
1721 m,
1722 );
1723 ComplexDMatrix::from_fn(m, n, |i, j| Complex::new(cr[i + j * m], ci[i + j * m]))
1724 }
1725
1726 pub(super) fn solve(f: &Factors, rhs: &ComplexDMatrix<f64>) -> ComplexDMatrix<f64> {
1728 let n = f.n;
1729 let k = rhs.ncols;
1730 let mut br = vec![0.0_f64; n * k];
1731 let mut bi = vec![0.0_f64; n * k];
1732 for c in 0..k {
1733 for i in 0..n {
1734 let z = rhs[(i, c)];
1735 br[i + c * n] = z.re;
1736 bi[i + c * n] = z.im;
1737 }
1738 }
1739 tpt_simd_blas::getrs_c64(n, k, &f.ar, &f.ai, n, &f.ipiv, &mut br, &mut bi, n);
1740 ComplexDMatrix::from_fn(n, k, |i, c| Complex::new(br[i + c * n], bi[i + c * n]))
1741 }
1742}
1743
1744#[cfg(all(test, feature = "simd-runtime"))]
1745mod simd_complex_tests {
1746 use super::*;
1747
1748 fn dominant(n: usize) -> ComplexDMatrix<f64> {
1749 ComplexDMatrix::from_fn(n, n, |i, j| {
1750 if i == j {
1751 Complex::new(n as f64 + 1.0, 0.5)
1752 } else {
1753 Complex::new(((i * 3 + j) as f64).sin(), ((i + 2 * j) as f64).cos() * 0.5)
1754 }
1755 })
1756 }
1757
1758 #[test]
1759 fn simd_lu_factors_agree_with_the_scalar_factors() {
1760 for n in [5usize, 33] {
1761 let a = dominant(n);
1762 let (l_s, u_s, p_s) = a.lu_with_tolerance(0.0).unwrap();
1763 let factors = simd_lu::factor(&a, 0.0).unwrap();
1764 let (l_v, u_v, p_v) = simd_lu::to_lu(&factors);
1765 assert_eq!(p_s, p_v, "permutation, n = {n}");
1766 for i in 0..n {
1767 for j in 0..n {
1768 let d = |x: Complex<f64>, y: Complex<f64>| (x.re - y.re).hypot(x.im - y.im);
1769 assert!(d(l_s[i][j], l_v[i][j]) < 1e-10, "L at ({i},{j}), n = {n}");
1770 assert!(d(u_s[i][j], u_v[i][j]) < 1e-10, "U at ({i},{j}), n = {n}");
1771 }
1772 }
1773 }
1774 }
1775
1776 #[test]
1777 fn simd_solve_and_inverse_have_small_residuals_above_the_cutoff() {
1778 let n = 80;
1779 let a = dominant(n);
1780 let b = ComplexDVector::from_fn(n, |i| Complex::new(i as f64, 1.0));
1781 let x = a.solve(&b).unwrap();
1782 for i in 0..n {
1783 let mut acc = Complex::new(0.0, 0.0);
1784 for j in 0..n {
1785 let (p, q) = (a[(i, j)], x[j]);
1786 acc = Complex::new(
1787 acc.re + p.re * q.re - p.im * q.im,
1788 acc.im + p.re * q.im + p.im * q.re,
1789 );
1790 }
1791 assert!((acc.re - b[i].re).hypot(acc.im - b[i].im) < 1e-9, "row {i}");
1792 }
1793 let inv = a.inverse().unwrap();
1794 for i in 0..n {
1795 for j in 0..n {
1796 let mut acc = Complex::new(0.0, 0.0);
1798 for k in 0..n {
1799 let (p, q) = (a[(i, k)], inv[(k, j)]);
1800 acc = Complex::new(
1801 acc.re + p.re * q.re - p.im * q.im,
1802 acc.im + p.re * q.im + p.im * q.re,
1803 );
1804 }
1805 let want = if i == j { 1.0 } else { 0.0 };
1806 assert!((acc.re - want).hypot(acc.im) < 1e-9, "({i},{j})");
1807 }
1808 }
1809 }
1810
1811 #[test]
1812 fn determinant_of_a_small_complex_matrix() {
1813 let a = ComplexDMatrix::from_fn(2, 2, |i, j| match (i, j) {
1815 (0, 0) => Complex::new(1.0, 1.0),
1816 (0, 1) => Complex::new(2.0, 0.0),
1817 (1, 0) => Complex::new(3.0, 0.0),
1818 _ => Complex::new(4.0, -1.0),
1819 });
1820 let d = a.det().unwrap();
1821 assert!(
1822 (d.re + 1.0).abs() < 1e-12 && (d.im - 3.0).abs() < 1e-12,
1823 "{d:?}"
1824 );
1825 }
1826
1827 #[test]
1828 fn determinant_sign_after_many_swaps_on_the_simd_path() {
1829 let n = 66;
1831 let shift = ComplexDMatrix::from_fn(n, n, |i, j| {
1832 Complex::new(if j == (i + 1) % n { 1.0 } else { 0.0 }, 0.0)
1833 });
1834 let d = shift.det().unwrap();
1835 assert!((d.re + 1.0).abs() < 1e-10 && d.im.abs() < 1e-10, "{d:?}");
1836 }
1837
1838 #[test]
1839 fn singular_determinant_is_zero_and_nonsquare_is_rejected() {
1840 let s = ComplexDMatrix::from_fn(2, 2, |_, _| Complex::new(1.0, 0.0));
1841 let d = s.det().unwrap();
1842 assert!(d.re == 0.0 && d.im == 0.0);
1843 assert!(ComplexDMatrix::from_fn(2, 3, |_, _| Complex::new(1.0, 0.0))
1844 .det()
1845 .is_err());
1846 }
1847
1848 #[test]
1849 fn product_matches_the_scalar_product_above_the_cutoff() {
1850 let n = 70;
1851 let a = dominant(n);
1852 let b = ComplexDMatrix::from_fn(n, n, |i, j| {
1853 Complex::new((i + 2 * j) as f64 * 0.01, (i as f64 - j as f64) * 0.02)
1854 });
1855 let fast = a.product(&b);
1856 let slow = a.clone() * b.clone();
1857 for i in 0..n {
1858 for j in 0..n {
1859 let (x, y) = (fast[(i, j)], slow[(i, j)]);
1860 assert!((x.re - y.re).hypot(x.im - y.im) < 1e-9, "({i},{j})");
1861 }
1862 }
1863 }
1864}