1use crate::internal_prelude::*;
20use complex::Complex;
21use equator::assert;
22pub use linalg::evd::ComputeEigenvectors;
23#[derive(Copy, Clone, Debug, PartialEq, Eq)]
25pub enum GevdError {
26 NoConvergence,
28}
29#[derive(Copy, Clone, Debug, PartialEq, Eq)]
31pub enum SelfAdjointGevdError {
32 NoConvergence,
34 NonPositiveDefinite,
36}
37#[derive(Clone, Copy, Debug)]
39pub struct GeneralizedSchurParams {
40 pub relative_cost_estimate_of_shift_chase_to_matmul: extern "C" fn(
43 matrix_dimension: usize,
44 active_block_dimension: usize,
45 )
46 -> usize,
47 pub recommended_shift_count: extern "C" fn(
50 matrix_dimension: usize,
51 active_block_dimension: usize,
52 ) -> usize,
53 pub recommended_deflation_window: extern "C" fn(
56 matrix_dimension: usize,
57 active_block_dimension: usize,
58 ) -> usize,
59 pub blocking_threshold: usize,
61 pub nibble_threshold: usize,
64 #[doc(hidden)]
65 pub non_exhaustive: NonExhaustive,
66}
67#[derive(Clone, Copy, Debug)]
69pub struct GevdFromSchurParams {
70 #[doc(hidden)]
71 pub non_exhaustive: NonExhaustive,
72}
73#[derive(Clone, Copy, Debug)]
75pub struct GevdParams {
76 pub hessenberg: gen_hessenberg::GeneralizedHessenbergParams,
78 pub schur: GeneralizedSchurParams,
80 pub evd_from_schur: GevdFromSchurParams,
82 #[doc(hidden)]
83 pub non_exhaustive: NonExhaustive,
84}
85extern "C" fn default_relative_cost_estimate_of_shift_chase_to_matmul(
86 n: usize,
87 nh: usize,
88) -> usize {
89 _ = (n, nh);
90 10
91}
92impl<T: ComplexField> Auto<T> for GeneralizedSchurParams {
93 fn auto() -> Self {
94 let schur: linalg::evd::SchurParams = auto!(T);
95 Self {
96 relative_cost_estimate_of_shift_chase_to_matmul:
97 default_relative_cost_estimate_of_shift_chase_to_matmul,
98 recommended_shift_count: schur.recommended_shift_count,
99 recommended_deflation_window: schur.recommended_deflation_window,
100 blocking_threshold: schur.blocking_threshold,
101 nibble_threshold: schur.nibble_threshold,
102 non_exhaustive: NonExhaustive(()),
103 }
104 }
105}
106impl<T: ComplexField> Auto<T> for GevdParams {
107 fn auto() -> Self {
108 Self {
109 hessenberg: auto!(T),
110 schur: auto!(T),
111 evd_from_schur: auto!(T),
112 non_exhaustive: NonExhaustive(()),
113 }
114 }
115}
116impl<T: ComplexField> Auto<T> for GevdFromSchurParams {
117 fn auto() -> Self {
118 Self {
119 non_exhaustive: NonExhaustive(()),
120 }
121 }
122}
123pub mod gen_hessenberg;
125pub mod qz_cplx;
127pub mod qz_real;
129#[track_caller]
130fn compute_gevd_generic<T: ComplexField>(
131 A: MatMut<'_, T>,
132 B: MatMut<'_, T>,
133 alpha_re: ColMut<'_, T>,
134 alpha_im: ColMut<'_, T>,
135 beta: ColMut<'_, T>,
136 u_left: Option<MatMut<'_, T>>,
137 u_right: Option<MatMut<'_, T>>,
138 par: Par,
139 stack: &mut MemStack,
140 params: GevdParams,
141 hessenberg_to_qz: fn(
142 A: MatMut<'_, T>,
143 B: MatMut<'_, T>,
144 Q: Option<MatMut<'_, T>>,
145 Z: Option<MatMut<'_, T>>,
146 alphar: ColMut<'_, T>,
147 alphai: ColMut<'_, T>,
148 beta: ColMut<'_, T>,
149 eigenvectors: ComputeEigenvectors,
150 par: Par,
151 params: GeneralizedSchurParams,
152 stack: &mut MemStack,
153 ),
154 qz_to_gevd: fn(
155 A: MatRef<'_, T>,
156 B: MatRef<'_, T>,
157 Q: Option<MatMut<'_, T>>,
158 Z: Option<MatMut<'_, T>>,
159 par: Par,
160 stack: &mut MemStack,
161 ),
162) -> Result<(), GevdError> {
163 let n = A.nrows();
164 assert!(all(
165 A.nrows() == n,
166 A.ncols() == n,
167 B.nrows() == n,
168 B.ncols() == n,
169 alpha_re.nrows() == n,
170 if const { T::IS_REAL } {
171 alpha_im.nrows()
172 } else {
173 n
174 } == n,
175 beta.nrows() == n,
176 ));
177 if let Some(u_left) = u_left.rb() {
178 assert!(all(u_left.nrows() == n, u_left.ncols() == n));
179 }
180 if let Some(u_right) = u_right.rb() {
181 assert!(all(u_right.nrows() == n, u_right.ncols() == n));
182 }
183 if n == 0 {
184 return Ok(());
185 }
186 #[cfg(feature = "perf-warn")]
187 {
188 for u in [u_left.rb(), u_right.rb()] {
189 if let Some(matrix) = u.rb() {
190 if matrix.row_stride().unsigned_abs() != 1
191 && crate::__perf_warn!(GEVD_WARN)
192 {
193 if matrix.col_stride().unsigned_abs() == 1 {
194 log::warn!(
195 target : "faer_perf",
196 "GEVD prefers column-major eigenvector matrix. Found row-major matrix."
197 );
198 } else {
199 log::warn!(
200 target : "faer_perf",
201 "GEVD prefers column-major eigenvector matrix. Found matrix with generic strides."
202 );
203 }
204 }
205 }
206 }
207 for M in [A.rb(), B.rb()] {
208 if M.row_stride().unsigned_abs() != 1
209 && crate::__perf_warn!(GEVD_WARN)
210 {
211 if M.col_stride().unsigned_abs() == 1 {
212 log::warn!(
213 target : "faer_perf",
214 "GEVD prefers column-major input matrix. Found row-major matrix."
215 );
216 } else {
217 log::warn!(
218 target : "faer_perf",
219 "GEVD prefers column-major input matrix. Found matrix with generic strides."
220 );
221 }
222 }
223 }
224 }
225 if !(A.is_all_finite() && B.is_all_finite()) {
226 { alpha_re }.fill(nan());
227 { alpha_im }.fill(nan());
228 { beta }.fill(nan());
229 for u in [u_left, u_right] {
230 if let Some(mut u) = u {
231 u.fill(nan());
232 }
233 }
234 return Err(GevdError::NoConvergence);
235 }
236 let need_qz = u_left.is_some() || u_right.is_some();
237 let mut A = A;
238 let mut B = B;
239 let mut u_left = u_left;
240 let mut u_right = u_right;
241 let mut alpha_re = alpha_re;
242 let mut alpha_im = alpha_im;
243 let mut beta = beta;
244 for u in [u_left.rb_mut(), u_right.rb_mut()] {
245 if let Some(u) = u {
246 u.diagonal_mut().column_vector_mut().fill(one());
247 }
248 }
249 {
250 let block_size =
251 linalg::qr::no_pivoting::factor::recommended_block_size::<T>(n, n);
252 let (mut householder, stack) =
253 unsafe { linalg::temp_mat_uninit::<T, _, _>(block_size, n, stack) };
254 let mut householder = householder.as_mat_mut();
255 linalg::qr::no_pivoting::factor::qr_in_place(
256 B.rb_mut(),
257 householder.rb_mut(),
258 par,
259 stack,
260 default(),
261 );
262 linalg::householder::apply_block_householder_sequence_transpose_on_the_left_in_place_with_conj(
263 B.rb(),
264 householder.rb(),
265 Conj::Yes,
266 A.rb_mut(),
267 par,
268 stack,
269 );
270 if let Some(u_left) = u_left.rb_mut() {
271 linalg::householder::apply_block_householder_sequence_on_the_left_in_place_with_conj(
272 B.rb(),
273 householder.rb(),
274 Conj::No,
275 u_left,
276 par,
277 stack,
278 );
279 }
280 zip!(B.rb_mut())
281 .for_each_triangular_lower(linalg::zip::Diag::Skip, |unzip!(x)| {
282 *x = zero()
283 });
284 }
285 gen_hessenberg::generalized_hessenberg(
286 A.rb_mut(),
287 B.rb_mut(),
288 u_left.rb_mut(),
289 u_right.rb_mut(),
290 par,
291 stack,
292 params.hessenberg,
293 );
294 hessenberg_to_qz(
295 A.rb_mut(),
296 B.rb_mut(),
297 u_left.rb_mut(),
298 u_right.rb_mut(),
299 alpha_re.rb_mut(),
300 alpha_im.rb_mut(),
301 beta.rb_mut(),
302 if need_qz {
303 ComputeEigenvectors::Yes
304 } else {
305 ComputeEigenvectors::No
306 },
307 par,
308 params.schur,
309 stack,
310 );
311 if !(alpha_re.is_all_finite()
315 && alpha_im.is_all_finite()
316 && beta.is_all_finite())
317 {
318 { alpha_re }.fill(nan());
319 { alpha_im }.fill(nan());
320 { beta }.fill(nan());
321 for mut u in [u_left, u_right].into_iter().flatten() {
322 u.fill(nan());
323 }
324 return Err(GevdError::NoConvergence);
325 }
326 qz_to_gevd(
327 A.rb(),
328 B.rb(),
329 u_left.rb_mut(),
330 u_right.rb_mut(),
331 par,
332 stack,
333 );
334 Ok(())
335}
336fn solve_shifted_1x1<T: ComplexField>(
337 smin: T::Real,
338 ca: T::Real,
339 A: T,
340 d0: T,
341 B: &mut T,
342 w: T,
343) {
344 let ref safmin = min_positive::<T::Real>();
345 let ref smlnum = safmin + safmin;
346 let ref smin = smin.fmax(smlnum);
347 let CR = A.mul_real(ca) - w * d0;
348 let cmax = CR.abs();
349 if cmax < *smin {
350 let smin_inv = smin.recip();
351 *B = B.mul_real(smin_inv);
352 }
353 let C = CR.recip();
354 *B *= C;
355}
356fn solve_complex_shifted_1x1<T: RealField>(
357 smin: T,
358 ca: T,
359 A: MatRef<'_, T>,
360 ref d0: T,
361 mut B: MatMut<'_, T>,
362 wr: T,
363 wi: T,
364) {
365 let nw = B.ncols();
366 let ref safmin = min_positive::<T>();
367 let ref smlnum = safmin + safmin;
368 let ref smin = smin.fmax(smlnum);
369 let CR = ca * &A[(0, 0)] - wr * d0;
370 let CI = -wi * d0;
371 let cmax = CR.abs().fmax(CI.abs());
372 if cmax < *smin {
373 let ref smin_inv = smin.recip();
374 zip!(B.rb_mut()).for_each(|unzip!(x)| *x *= smin_inv);
375 }
376 if nw == 1 {
377 let ref C = CR.recip();
378 zip!(B.rb_mut()).for_each(|unzip!(x)| *x *= C);
379 } else {
380 let (Br, Bi) = B.two_cols_mut(0, 1);
381 let C = Complex { re: CR, im: CI }.recip();
382 zip!(Br, Bi).for_each(|unzip!(re, im)| {
383 (*re, *im) =
384 (&*re * &C.re - &*im * &C.im, &*re * &C.im + &*im * &C.re);
385 });
386 }
387}
388fn solve_complex_shifted_2x2<T: RealField>(
389 smin: T,
390 ref ca: T,
391 A: MatRef<'_, T>,
392 ref d0: T,
393 ref d1: T,
394 mut B: MatMut<'_, T>,
395 ref wr: T,
396 ref wi: T,
397 stack: &mut MemStack,
398) {
399 let nw = B.ncols();
400 let zero = zero::<T>;
401 let ref safmin = min_positive::<T>();
402 let ref smlnum = safmin + safmin;
403 let ref smin = smin.fmax(smlnum);
404 if nw == 1 {
405 let (mut C, stack) =
406 unsafe { linalg::temp_mat_uninit::<T, _, _>(2, 2, stack) };
407 let mut C = C.as_mat_mut();
408 let mut row_perm_fwd = [0usize; 2];
409 let mut row_perm_inv = [0usize; 2];
410 let mut col_perm_fwd = [0usize; 2];
411 let mut col_perm_inv = [0usize; 2];
412 C[(0, 0)] = ca * &A[(0, 0)] - wr * d0;
413 C[(1, 0)] = ca * &A[(1, 0)];
414 C[(0, 1)] = ca * &A[(0, 1)];
415 C[(1, 1)] = ca * &A[(1, 1)] - wr * d1;
416 let cmax = C.norm_max();
417 if cmax < *smin {
418 let ref smin_inv = smin.recip();
419 zip!(B.rb_mut()).for_each(|unzip!(x)| *x *= smin_inv);
420 }
421 let (_, row_perm, col_perm) =
422 linalg::lu::full_pivoting::factor::lu_in_place(
423 C.rb_mut(),
424 &mut row_perm_fwd,
425 &mut row_perm_inv,
426 &mut col_perm_fwd,
427 &mut col_perm_inv,
428 Par::Seq,
429 stack,
430 Default::default(),
431 );
432 linalg::lu::full_pivoting::solve::solve_in_place(
433 C.rb(),
434 C.rb(),
435 row_perm,
436 col_perm,
437 B.rb_mut(),
438 Par::Seq,
439 stack,
440 );
441 } else {
442 let (mut C, stack) =
443 unsafe { linalg::temp_mat_uninit::<Complex<T>, _, _>(2, 2, stack) };
444 let mut C = C.as_mat_mut();
445 let mut row_perm_fwd = [0usize; 2];
446 let mut row_perm_inv = [0usize; 2];
447 let mut col_perm_fwd = [0usize; 2];
448 let mut col_perm_inv = [0usize; 2];
449 C[(0, 0)] = Complex {
450 re: ca * &A[(0, 0)] - wr * d0,
451 im: -wi * d0,
452 };
453 C[(1, 0)] = Complex {
454 re: ca * &A[(1, 0)],
455 im: zero(),
456 };
457 C[(0, 1)] = Complex {
458 re: ca * &A[(0, 1)],
459 im: zero(),
460 };
461 C[(1, 1)] = Complex {
462 re: ca * &A[(1, 1)] - wr * d1,
463 im: -wi * d1,
464 };
465 let cmax = C.norm_max();
466 if cmax < *smin {
467 let ref smin_inv = smin.recip();
468 zip!(B.rb_mut()).for_each(|unzip!(x)| *x *= smin_inv);
469 }
470 let (_, row_perm, col_perm) =
471 linalg::lu::full_pivoting::factor::lu_in_place(
472 C.rb_mut(),
473 &mut row_perm_fwd,
474 &mut row_perm_inv,
475 &mut col_perm_fwd,
476 &mut col_perm_inv,
477 Par::Seq,
478 stack,
479 Default::default(),
480 );
481 let n = B.nrows();
482 let (Br, Bi) = B.two_cols_mut(0, 1);
483 let (mut B, stack) =
484 unsafe { linalg::temp_mat_uninit::<Complex<T>, _, _>(n, 1, stack) };
485 let mut B = B.as_mat_mut().col_mut(0);
486 zip!(&mut B, &Br, &Bi).for_each(|unzip!(z, re, im)| {
487 *z = Complex {
488 re: re.copy(),
489 im: im.copy(),
490 }
491 });
492 linalg::lu::full_pivoting::solve::solve_in_place(
493 C.rb(),
494 C.rb(),
495 row_perm,
496 col_perm,
497 B.rb_mut().as_mat_mut(),
498 Par::Seq,
499 stack,
500 );
501 zip!(Br, Bi, &B).for_each(|unzip!(re, im, z)| {
502 (*re, *im) = (z.re.copy(), z.im.copy())
503 });
504 }
505}
506fn qz_to_gevd_real<T: RealField>(
507 A: MatRef<'_, T>,
508 B: MatRef<'_, T>,
509 Q: Option<MatMut<'_, T>>,
510 Z: Option<MatMut<'_, T>>,
511 par: Par,
512 stack: &mut MemStack,
513) {
514 let n = A.nrows();
515 if n == 0 {
516 return;
517 }
518 let one = one::<T>;
519 let zero = zero::<T>;
520 let ref ulp = eps::<T>();
521 let ref safmin = min_positive::<T>();
522 let ref smallnum = safmin * from_f64::<T::Real>(n as f64);
523 let ref small = smallnum * ulp.recip();
524 let ref bignum = smallnum.recip();
525 let ref big = small.recip();
526 let (mut acolnorm, stack) = linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
527 let acolnorm = acolnorm.as_mat_mut();
528 let (mut bcolnorm, stack) = linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
529 let bcolnorm = bcolnorm.as_mat_mut();
530 let mut acolnorm = acolnorm.col_mut(0);
531 let mut bcolnorm = bcolnorm.col_mut(0);
532 let mut anorm = zero();
533 let mut bnorm = zero();
534 let mut j = 0;
535 while j < n {
536 let cplx = j + 1 < n && A[(j + 1, j)] != zero();
537 if !cplx {
538 let a = A.rb().col(j).get(..j).norm_l1();
539 acolnorm[j] = a.copy();
540 anorm = anorm.fmax(a + A[(j, j)].abs());
541 j += 1;
542 } else {
543 for jc in j..j + 2 {
544 let a = A.rb().col(jc).get(..j).norm_l1();
545 acolnorm[jc] = a.copy();
546 anorm = anorm.fmax(a + A[(j, jc)].abs() + A[(j + 1, jc)].abs());
547 }
548 j += 2;
549 }
550 }
551 for j in 0..n {
552 let b = B.rb().col(j).get(..j).norm_l1();
553 bcolnorm[j] = b.copy();
554 bnorm = bnorm.fmax(b + B[(j, j)].abs());
555 }
556 let ref anorm = anorm;
557 let ref bnorm = bnorm;
558 let ref ascale = anorm.fmax(safmin).recip();
559 let ref bscale = bnorm.fmax(safmin).recip();
560 if let Some(mut u) = Q {
561 let mut je = 0usize;
562 while je < n {
563 let cplx_eigval = je + 1 < n && A[(je + 1, je)] != zero();
564 let nw = if cplx_eigval { 2 } else { 1 };
565 if !cplx_eigval
566 && A[(je, je)].abs().fmax(&B[(je, je)].abs()) < *safmin
567 {
568 u.rb_mut().col_mut(je).fill(zero());
569 u[(je, je)] = one();
570 je += 1;
571 continue;
572 }
573 let mut acoef;
574 let mut acoefa;
575 let mut bcoefa;
576 let mut bcoefr;
577 let mut bcoefi;
578 let mut xmax;
579 let (mut rhs, stack) =
580 linalg::temp_mat_zeroed::<T, _, _>(n, nw, stack);
581 let mut rhs = rhs.as_mat_mut();
582 if !cplx_eigval {
583 let ref temp = safmin.fmax(
584 (A[(je, je)].abs() * ascale)
585 .fmax(B[(je, je)].abs() * bscale),
586 );
587 let ref salfar = A[(je, je)].mul_real(temp).mul_real(ascale);
588 let ref sbeta = B[(je, je)].real() * temp * bscale;
589 acoef = sbeta * ascale;
590 bcoefr = salfar * bscale;
591 bcoefi = zero();
592 let mut scale = one();
593 let lsa = sbeta.abs() >= *safmin && acoef.abs() < *small;
594 let lsb = salfar.abs() >= *safmin && bcoefr.abs() < *small;
595 if lsa {
596 scale = (small / sbeta.abs()) * anorm.fmin(big);
597 }
598 if lsb {
599 scale =
600 scale.fmax((small / salfar.abs()) * bnorm.fmin(big));
601 }
602 if lsa || lsb {
603 scale = scale.fmin(
604 one()
605 / (safmin
606 * one().fmax(acoef.abs()).fmax(bcoefr.abs())),
607 );
608 if lsa {
609 acoef = ascale * (&scale * sbeta)
610 } else {
611 acoef = &scale * acoef
612 }
613 if lsb {
614 bcoefr = bscale * (&scale * salfar)
615 } else {
616 bcoefr = &scale * bcoefr
617 }
618 }
619 acoefa = acoef.abs();
620 bcoefa = bcoefr.abs();
621 rhs[(je, 0)] = one();
622 xmax = one();
623 } else {
624 let (ref scale, _, wr, _, wi) = qz_real::generalized_eigval_2x2(
625 (
626 A[(je, je)].copy(),
627 A[(je, je + 1)].copy(),
628 A[(je + 1, je)].copy(),
629 A[(je + 1, je + 1)].copy(),
630 ),
631 (
632 B[(je, je)].copy(),
633 B[(je, je + 1)].copy(),
634 B[(je + 1, je)].copy(),
635 B[(je + 1, je + 1)].copy(),
636 ),
637 );
638 acoef = scale.copy();
639 bcoefr = wr;
640 bcoefi = wi;
641 acoefa = acoef.abs();
642 bcoefa = bcoefr.abs() + bcoefi.abs();
643 let mut scale = one();
644 if &acoefa * ulp < *safmin && acoefa >= *safmin {
645 scale = (safmin / ulp) / &acoefa;
646 }
647 if &bcoefa * ulp < *safmin && bcoefa >= *safmin {
648 scale = scale.fmax((safmin / ulp) / &bcoefa);
649 }
650 if safmin * &acoefa > *ascale {
651 scale = ascale / (safmin * &acoefa);
652 }
653 if safmin * &bcoefa > *bscale {
654 scale = scale.fmin(bscale / (safmin * &bcoefa));
655 }
656 if scale != one() {
657 acoef = &scale * &acoef;
658 acoefa = acoef.abs();
659 bcoefr = &scale * &bcoefr;
660 bcoefi = &scale * &bcoefi;
661 bcoefa = bcoefr.abs() + bcoefi.abs();
662 }
663 let ref temp = &acoef * &A[(je + 1, je)];
664 let temp2r = &acoef * &A[(je, je)] - &bcoefr * &B[(je, je)];
665 let temp2i = -&bcoefi * &B[(je, je)];
666 if temp.abs() > temp2r.abs() + temp2i.abs() {
667 rhs[(je, 0)] = one();
668 rhs[(je, 1)] = zero();
669 rhs[(je + 1, 0)] = -temp2r / temp;
670 rhs[(je + 1, 1)] = -temp2i / temp;
671 } else {
672 rhs[(je + 1, 0)] = one();
673 rhs[(je + 1, 1)] = zero();
674 let ref temp = &acoef * &A[(je, je + 1)];
675 rhs[(je, 0)] = (&bcoefr * &B[(je + 1, je + 1)]
676 - &acoef * &A[(je + 1, je + 1)])
677 / temp;
678 rhs[(je, 1)] = &bcoefi * &B[(je + 1, je + 1)] / temp;
679 }
680 xmax = (rhs[(je, 0)].abs() + rhs[(je, 1)].abs())
681 .fmax(rhs[(je + 1, 0)].abs() + rhs[(je + 1, 1)].abs());
682 }
683 let dmin = safmin
684 .fmax(ulp * &acoefa * anorm)
685 .fmax(ulp * &bcoefa * bnorm);
686 let mut j = je + nw;
687 while j < n {
688 let cplx = j + 1 < n && A[(j + 1, j)] != zero();
689 let na = if cplx { 2 } else { 1 };
690 let ref xscale = xmax.recip();
691 let mut temp = acolnorm[j]
692 .fmax(&bcolnorm[j])
693 .fmax(&acoefa * &acolnorm[j] + &bcoefa * &bcolnorm[j]);
694 let b0 = B[(j, j)].copy();
695 let b1;
696 if cplx {
697 temp = temp
698 .fmax(
699 &acoefa * &acolnorm[j + 1]
700 + &bcoefa * &bcolnorm[j + 1],
701 )
702 .fmax(&acolnorm[j + 1])
703 .fmax(&acolnorm[j + 1]);
704 b1 = B[(j + 1, j + 1)].copy();
705 } else {
706 b1 = zero();
707 }
708 if temp > bignum * xscale {
709 for jw in 0..nw {
710 for jr in je..j {
711 rhs[(jr, jw)] = xscale * &rhs[(jr, jw)];
712 }
713 }
714 xmax = xmax * xscale;
715 }
716 let (mut sums, stack) = unsafe {
717 linalg::temp_mat_uninit::<T, _, _>(na, nw, stack)
718 };
719 let mut sums = sums.as_mat_mut();
720 let (mut sump, stack) = unsafe {
721 linalg::temp_mat_uninit::<T, _, _>(na, nw, stack)
722 };
723 let mut sump = sump.as_mat_mut();
724 for jw in 0..nw {
725 for ja in 0..na {
726 sums[(ja, jw)] = zero();
727 sump[(ja, jw)] = zero();
728 for jr in je..j {
729 sums[(ja, jw)] = &sums[(ja, jw)]
730 + &A[(jr, j + ja)] * &rhs[(jr, jw)];
731 sump[(ja, jw)] = &sump[(ja, jw)]
732 + &B[(jr, j + ja)] * &rhs[(jr, jw)];
733 }
734 }
735 }
736 for ja in 0..na {
737 if cplx_eigval {
738 rhs[(j + ja, 0)] = -&acoef * &sums[(ja, 0)]
739 + &bcoefr * &sump[(ja, 0)]
740 - &bcoefi * &sump[(ja, 1)];
741 rhs[(j + ja, 1)] = -&acoef * &sums[(ja, 1)]
742 + &bcoefr * &sump[(ja, 1)]
743 + &bcoefi * &sump[(ja, 0)];
744 } else {
745 rhs[(j + ja, 0)] =
746 -&acoef * &sums[(ja, 0)] + &bcoefr * &sump[(ja, 0)];
747 }
748 }
749 if cplx {
750 solve_complex_shifted_2x2(
751 dmin.copy(),
752 acoef.copy(),
753 A.submatrix(j, j, na, na).transpose(),
754 b0,
755 b1,
756 rhs.rb_mut().subrows_mut(j, na),
757 bcoefr.copy(),
758 bcoefi.copy(),
759 stack,
760 );
761 } else {
762 solve_complex_shifted_1x1(
763 dmin.copy(),
764 acoef.copy(),
765 A.submatrix(j, j, na, na).transpose(),
766 b0,
767 rhs.rb_mut().subrows_mut(j, na),
768 bcoefr.copy(),
769 bcoefi.copy(),
770 );
771 }
772 j += na;
773 }
774 let (mut tmp, _) = linalg::temp_mat_zeroed::<T, _, _>(n, nw, stack);
775 let mut tmp = tmp.as_mat_mut();
776 linalg::matmul::matmul(
777 tmp.rb_mut(),
778 Accum::Replace,
779 u.rb().get(.., je..),
780 rhs.rb().get(je.., ..),
781 one(),
782 par,
783 );
784 let mut u = u.rb_mut().subcols_mut(je, nw);
785 u.copy_from(&tmp);
786 let ref scale = u.norm_l2().recip();
787 zip!(u).for_each(|unzip!(u)| {
788 *u *= scale;
789 });
790 je += nw;
791 }
792 }
793 if let Some(mut u) = Z {
794 let mut je = n;
795 while je > 0 {
796 je -= 1;
797 let cplx_eigval = je > 0 && A[(je, je - 1)] != zero();
798 let nw = if cplx_eigval { 2 } else { 1 };
799 je -= nw - 1;
800 if !cplx_eigval
801 && A[(je, je)].abs().fmax(&B[(je, je)].abs()) < *safmin
802 {
803 u.rb_mut().col_mut(je).fill(zero());
804 u[(je, je)] = one();
805 continue;
806 }
807 let mut acoef;
808 let mut acoefa;
809 let mut bcoefa;
810 let mut bcoefr;
811 let mut bcoefi;
812 let (mut rhs, stack) =
813 linalg::temp_mat_zeroed::<T, _, _>(n, nw, stack);
814 let mut rhs = rhs.as_mat_mut();
815 if !cplx_eigval {
816 let ref temp = safmin.fmax(
817 (A[(je, je)].abs() * ascale)
818 .fmax(B[(je, je)].abs() * bscale),
819 );
820 let ref salfar = A[(je, je)].mul_real(temp).mul_real(ascale);
821 let ref sbeta = B[(je, je)].real() * temp * bscale;
822 acoef = sbeta * ascale;
823 bcoefr = salfar * bscale;
824 bcoefi = zero();
825 let mut scale = one();
826 let lsa = sbeta.abs() >= *safmin && acoef.abs() < *small;
827 let lsb = salfar.abs() >= *safmin && bcoefr.abs() < *small;
828 if lsa {
829 scale = (small / sbeta.abs()) * anorm.fmin(big);
830 }
831 if lsb {
832 scale =
833 scale.fmax((small / salfar.abs()) * bnorm.fmin(big));
834 }
835 if lsa || lsb {
836 scale = scale.fmin(
837 one()
838 / (safmin
839 * one().fmax(acoef.abs()).fmax(bcoefr.abs())),
840 );
841 if lsa {
842 acoef = ascale * (&scale * sbeta)
843 } else {
844 acoef = &scale * &acoef
845 }
846 if lsb {
847 bcoefr = bscale * (&scale * salfar)
848 } else {
849 bcoefr = &scale * &bcoefr
850 }
851 }
852 acoefa = acoef.abs();
853 bcoefa = bcoefr.abs();
854 rhs[(je, 0)] = one();
855 for jr in 0..je {
856 rhs[(jr, 0)] =
857 &bcoefr * &B[(jr, je)] - &acoef * &A[(jr, je)];
858 }
859 } else {
860 let (scale, _, wr, _, wi) = qz_real::generalized_eigval_2x2(
861 (
862 A[(je, je)].copy(),
863 A[(je, je + 1)].copy(),
864 A[(je + 1, je)].copy(),
865 A[(je + 1, je + 1)].copy(),
866 ),
867 (
868 B[(je, je)].copy(),
869 B[(je, je + 1)].copy(),
870 B[(je + 1, je)].copy(),
871 B[(je + 1, je + 1)].copy(),
872 ),
873 );
874 acoef = scale;
875 bcoefr = wr;
876 bcoefi = wi;
877 acoefa = acoef.abs();
878 bcoefa = bcoefr.abs() + bcoefi.abs();
879 let mut scale = one();
880 if &acoefa * ulp < *safmin && acoefa >= *safmin {
881 scale = (safmin / ulp) / &acoefa;
882 }
883 if &bcoefa * ulp < *safmin && bcoefa >= *safmin {
884 scale = scale.fmax((safmin / ulp) / &bcoefa);
885 }
886 if safmin * &acoefa > *ascale {
887 scale = ascale / (safmin * &acoefa);
888 }
889 if safmin * &bcoefa > *bscale {
890 scale = scale.fmin(bscale / (safmin * &bcoefa));
891 }
892 if scale != one() {
893 acoef = &scale * &acoef;
894 acoefa = acoef.abs();
895 bcoefr = &scale * &bcoefr;
896 bcoefi = &scale * &bcoefi;
897 bcoefa = bcoefr.abs() + bcoefi.abs();
898 }
899 let ref temp = &acoef * &A[(je + 1, je)];
900 let ref temp2r = &acoef * &A[(je + 1, je + 1)]
901 - &bcoefr * &B[(je + 1, je + 1)];
902 let ref temp2i = -&bcoefi * &B[(je + 1, je + 1)];
903 if temp.abs() > temp2r.abs() + temp2i.abs() {
904 rhs[(je + 1, 0)] = one();
905 rhs[(je + 1, 1)] = zero();
906 rhs[(je, 0)] = -temp2r / temp;
907 rhs[(je, 1)] = -temp2i / temp;
908 } else {
909 rhs[(je, 0)] = one();
910 rhs[(je, 1)] = zero();
911 let ref temp = &acoef * &A[(je, je + 1)];
912 rhs[(je + 1, 0)] =
913 (&bcoefr * &B[(je, je)] - &acoef * &A[(je, je)]) / temp;
914 rhs[(je + 1, 1)] = &bcoefi * &B[(je, je)] / temp;
915 }
916 let ref creala = &acoef * &rhs[(je, 0)];
917 let ref cimaga = &acoef * &rhs[(je, 1)];
918 let ref crealb =
919 &bcoefr * &rhs[(je, 0)] - &bcoefi * &rhs[(je, 1)];
920 let ref cimagb =
921 &bcoefi * &rhs[(je, 0)] + &bcoefr * &rhs[(je, 1)];
922 let ref cre2a = &acoef * &rhs[(je + 1, 0)];
923 let ref cim2a = &acoef * &rhs[(je + 1, 1)];
924 let ref cre2b =
925 &bcoefr * &rhs[(je + 1, 0)] - &bcoefi * &rhs[(je + 1, 1)];
926 let ref cim2b =
927 &bcoefi * &rhs[(je + 1, 0)] + &bcoefr * &rhs[(je + 1, 1)];
928 for jr in 0..je {
929 rhs[(jr, 0)] = -creala * &A[(jr, je)]
930 + crealb * &B[(jr, je)]
931 - cre2a * &A[(jr, je + 1)]
932 + cre2b * &B[(jr, je + 1)];
933 rhs[(jr, 1)] = -cimaga * &A[(jr, je)]
934 + cimagb * &B[(jr, je)]
935 - cim2a * &A[(jr, je + 1)]
936 + cim2b * &B[(jr, je + 1)];
937 }
938 }
939 let dmin = safmin
940 .fmax(ulp * &acoefa * anorm)
941 .fmax(ulp * &bcoefa * bnorm);
942 let mut j = je;
943 while j > 0 {
944 j -= 1;
945 let cplx = j > 0 && A[(j, j - 1)] != zero();
946 let na = if cplx { 2 } else { 1 };
947 j -= na - 1;
948 let b0 = B[(j, j)].copy();
949 let b1;
950 if cplx {
951 b1 = B[(j + 1, j + 1)].copy();
952 } else {
953 b1 = zero();
954 }
955 if cplx {
956 solve_complex_shifted_2x2(
957 dmin.copy(),
958 acoef.copy(),
959 A.submatrix(j, j, na, na),
960 b0,
961 b1,
962 rhs.rb_mut().subrows_mut(j, na),
963 bcoefr.copy(),
964 bcoefi.copy(),
965 stack,
966 );
967 } else {
968 solve_complex_shifted_1x1(
969 dmin.copy(),
970 acoef.copy(),
971 A.submatrix(j, j, na, na),
972 b0,
973 rhs.rb_mut().subrows_mut(j, na),
974 bcoefr.copy(),
975 bcoefi.copy(),
976 );
977 }
978 for ja in 0..na {
979 if cplx_eigval {
980 let ref creala = &acoef * &rhs[(j + ja, 0)];
981 let ref cimaga = &acoef * &rhs[(j + ja, 1)];
982 let ref crealb = &bcoefr * &rhs[(j + ja, 0)]
983 - &bcoefi * &rhs[(j + ja, 1)];
984 let ref cimagb = &bcoefi * &rhs[(j + ja, 0)]
985 + &bcoefr * &rhs[(j + ja, 1)];
986 for jr in 0..j {
987 rhs[(jr, 0)] -= creala * &A[(jr, j + ja)]
988 - crealb * &B[(jr, j + ja)];
989 rhs[(jr, 1)] -= cimaga * &A[(jr, j + ja)]
990 - cimagb * &B[(jr, j + ja)];
991 }
992 } else {
993 let ref creala = &acoef * &rhs[(j + ja, 0)];
994 let ref crealb = &bcoefr * &rhs[(j + ja, 0)];
995 for jr in 0..j {
996 rhs[(jr, 0)] -= creala * &A[(jr, j + ja)]
997 - crealb * &B[(jr, j + ja)];
998 }
999 }
1000 }
1001 }
1002 let (mut tmp, _) = linalg::temp_mat_zeroed::<T, _, _>(n, nw, stack);
1003 let mut tmp = tmp.as_mat_mut();
1004 linalg::matmul::matmul(
1005 tmp.rb_mut(),
1006 Accum::Replace,
1007 u.rb().get(.., ..je + nw),
1008 rhs.rb().get(..je + nw, ..),
1009 one(),
1010 par,
1011 );
1012 let mut u = u.rb_mut().subcols_mut(je, nw);
1013 u.copy_from(&tmp);
1014 let ref scale = u.norm_l2().recip();
1015 zip!(u).for_each(|unzip!(u)| {
1016 *u *= scale;
1017 });
1018 }
1019 }
1020}
1021fn qz_to_gevd_cplx<T: ComplexField>(
1022 A: MatRef<'_, T>,
1023 B: MatRef<'_, T>,
1024 Q: Option<MatMut<'_, T>>,
1025 Z: Option<MatMut<'_, T>>,
1026 par: Par,
1027 stack: &mut MemStack,
1028) {
1029 let n = A.nrows();
1030 if n == 0 {
1031 return;
1032 }
1033 let one = one::<T::Real>;
1034 let ref ulp = eps::<T::Real>();
1035 let ref safmin = min_positive::<T::Real>();
1036 let ref smallnum = safmin * from_f64::<T::Real>(n as f64);
1037 let ref small = smallnum * ulp.recip();
1038 let ref bignum = smallnum.recip();
1039 let ref big = small.recip();
1040 let (mut acolnorm, stack) =
1041 linalg::temp_mat_zeroed::<T::Real, _, _>(n, 1, stack);
1042 let acolnorm = acolnorm.as_mat_mut();
1043 let (mut bcolnorm, stack) =
1044 linalg::temp_mat_zeroed::<T::Real, _, _>(n, 1, stack);
1045 let bcolnorm = bcolnorm.as_mat_mut();
1046 let mut acolnorm = acolnorm.col_mut(0);
1047 let mut bcolnorm = bcolnorm.col_mut(0);
1048 let mut anorm = zero::<T::Real>();
1049 let mut bnorm = zero::<T::Real>();
1050 let mut j = 0;
1051 while j < n {
1052 let a = A.rb().col(j).get(..j).norm_l1();
1053 acolnorm[j] = a.copy();
1054 anorm = anorm.fmax(a + A[(j, j)].abs());
1055 j += 1;
1056 }
1057 for j in 0..n {
1058 let ref b = B.rb().col(j).get(..j).norm_l1();
1059 bcolnorm[j] = b.copy();
1060 bnorm = bnorm.fmax(b + B[(j, j)].abs());
1061 }
1062 let ref anorm = anorm;
1063 let ref bnorm = bnorm;
1064 let ref ascale = anorm.fmax(safmin).recip();
1065 let ref bscale = bnorm.fmax(safmin).recip();
1066 if let Some(mut u) = Q {
1067 let mut je = 0usize;
1068 while je < n {
1069 if A[(je, je)].abs().fmax(&B[(je, je)].abs()) < *safmin {
1070 u.rb_mut().col_mut(je).fill(zero());
1071 u[(je, je)] = one().to_cplx();
1072 je += 1;
1073 continue;
1074 }
1075 let mut acoef;
1076 let acoefa;
1077 let bcoefa;
1078 let mut bcoef;
1079 let mut xmax;
1080 let (mut rhs, stack) =
1081 linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
1082 let mut rhs = rhs.as_mat_mut().col_mut(0);
1083 {
1084 let ref temp = safmin.fmax(
1085 (A[(je, je)].abs() * ascale)
1086 .fmax(B[(je, je)].abs() * bscale),
1087 );
1088 let ref salfar = A[(je, je)].mul_real(temp).mul_real(ascale);
1089 let ref sbeta = B[(je, je)].real() * temp * bscale;
1090 acoef = sbeta * ascale;
1091 bcoef = salfar.mul_real(bscale);
1092 let mut scale = one();
1093 let lsa = sbeta.abs() >= *safmin && acoef.abs() < *small;
1094 let lsb = salfar.abs() >= *safmin && bcoef.abs() < *small;
1095 if lsa {
1096 scale = (small / sbeta.abs()) * anorm.fmin(big);
1097 }
1098 if lsb {
1099 scale =
1100 scale.fmax((small / salfar.abs()) * bnorm.fmin(big));
1101 }
1102 if lsa || lsb {
1103 scale = scale.fmin(
1104 one()
1105 / (safmin
1106 * one().fmax(acoef.abs()).fmax(bcoef.abs())),
1107 );
1108 if lsa {
1109 acoef = sbeta * &scale * ascale
1110 } else {
1111 acoef = acoef * &scale
1112 }
1113 if lsb {
1114 bcoef = salfar.mul_real(&scale).mul_real(bscale)
1115 } else {
1116 bcoef = bcoef.mul_real(&scale)
1117 }
1118 }
1119 acoefa = acoef.abs();
1120 bcoefa = bcoef.abs();
1121 rhs[je] = one().to_cplx();
1122 xmax = one();
1123 }
1124 let dmin = safmin
1125 .fmax(ulp * &acoefa * anorm)
1126 .fmax(ulp * &bcoefa * bnorm);
1127 let mut j = je + 1;
1128 while j < n {
1129 let ref xscale = xmax.recip();
1130 let ref temp = acolnorm[j]
1131 .fmax(&bcolnorm[j])
1132 .fmax(&acoefa * &acolnorm[j] + &bcoefa * &bcolnorm[j]);
1133 let b0 = B[(j, j)].copy();
1134 if *temp > bignum * xscale {
1135 for jr in je..j {
1136 rhs[jr] = rhs[jr].mul_real(xscale);
1137 }
1138 xmax = xmax * xscale;
1139 }
1140 let mut sums = zero::<T>();
1141 let mut sump = zero::<T>();
1142 for jr in je..j {
1143 sums += A[(jr, j)].conj() * &rhs[jr];
1144 sump += B[(jr, j)].conj() * &rhs[jr];
1145 }
1146 rhs[j] = bcoef.conj() * &sump - sums.mul_real(&acoef);
1147 solve_shifted_1x1(
1148 dmin.copy(),
1149 acoef.copy(),
1150 A[(j, j)].conj(),
1151 b0.conj(),
1152 &mut rhs[j],
1153 bcoef.conj(),
1154 );
1155 j += 1;
1156 }
1157 let (mut tmp, _) = linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
1158 let mut tmp = tmp.as_mat_mut().col_mut(0);
1159 linalg::matmul::matmul(
1160 tmp.rb_mut(),
1161 Accum::Replace,
1162 u.rb().get(.., je..),
1163 rhs.rb().get(je..),
1164 one().to_cplx(),
1165 par,
1166 );
1167 let mut u = u.rb_mut().col_mut(je);
1168 u.copy_from(&tmp);
1169 let ref scale = u.norm_l2().recip();
1170 zip!(u).for_each(|unzip!(u)| {
1171 *u = u.mul_real(scale);
1172 });
1173 je += 1;
1174 }
1175 }
1176 if let Some(mut u) = Z {
1177 let mut je = n;
1178 while je > 0 {
1179 je -= 1;
1180 if A[(je, je)].abs().fmax(&B[(je, je)].abs()) < *safmin {
1181 u.rb_mut().col_mut(je).fill(zero());
1182 u[(je, je)] = one().to_cplx();
1183 continue;
1184 }
1185 let mut acoef;
1186 let acoefa;
1187 let bcoefa;
1188 let mut bcoefr;
1189 let (mut rhs, stack) =
1190 linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
1191 let mut rhs = rhs.as_mat_mut().col_mut(0);
1192 {
1193 let ref temp = safmin.fmax(
1194 (A[(je, je)].abs() * ascale)
1195 .fmax(B[(je, je)].abs() * bscale),
1196 );
1197 let ref salfar = A[(je, je)].mul_real(temp).mul_real(ascale);
1198 let ref sbeta = B[(je, je)].real() * temp * bscale;
1199 acoef = sbeta * ascale;
1200 bcoefr = salfar.mul_real(bscale);
1201 let mut scale = one();
1202 let lsa = sbeta.abs() >= *safmin && acoef.abs() < *small;
1203 let lsb = salfar.abs() >= *safmin && bcoefr.abs() < *small;
1204 if lsa {
1205 scale = (small / sbeta.abs()) * anorm.fmin(big);
1206 }
1207 if lsb {
1208 scale =
1209 scale.fmax((small / salfar.abs()) * bnorm.fmin(big));
1210 }
1211 if lsa || lsb {
1212 scale = scale.fmin(
1213 one()
1214 / (safmin
1215 * one().fmax(acoef.abs()).fmax(bcoefr.abs())),
1216 );
1217 if lsa {
1218 acoef = sbeta * &scale * ascale
1219 } else {
1220 acoef = acoef * &scale
1221 }
1222 if lsb {
1223 bcoefr = salfar.mul_real(&scale).mul_real(bscale)
1224 } else {
1225 bcoefr = bcoefr.mul_real(&scale)
1226 }
1227 }
1228 acoefa = acoef.abs();
1229 bcoefa = bcoefr.abs();
1230 rhs[je] = one().to_cplx();
1231 for jr in 0..je {
1232 rhs[jr] =
1233 &bcoefr * &B[(jr, je)] - A[(jr, je)].mul_real(&acoef);
1234 }
1235 }
1236 let dmin = safmin
1237 .fmax(ulp * &acoefa * anorm)
1238 .fmax(ulp * &bcoefa * bnorm);
1239 let mut j = je;
1240 while j > 0 {
1241 j -= 1;
1242 let b0 = B[(j, j)].copy();
1243 solve_shifted_1x1(
1244 dmin.copy(),
1245 acoef.copy(),
1246 A[(j, j)].copy(),
1247 b0,
1248 &mut rhs[j],
1249 bcoefr.copy(),
1250 );
1251 let ref creala = rhs[j].mul_real(&acoef);
1252 let ref crealb = &bcoefr * &rhs[j];
1253 for jr in 0..j {
1254 rhs[jr] =
1255 &rhs[jr] - creala * &A[(jr, j)] + crealb * &B[(jr, j)];
1256 }
1257 }
1258 let (mut tmp, _) = linalg::temp_mat_zeroed::<T, _, _>(n, 1, stack);
1259 let mut tmp = tmp.as_mat_mut().col_mut(0);
1260 linalg::matmul::matmul(
1261 tmp.rb_mut(),
1262 Accum::Replace,
1263 u.rb().get(.., ..je + 1),
1264 rhs.rb().get(..je + 1),
1265 one().to_cplx(),
1266 par,
1267 );
1268 let mut u = u.rb_mut().col_mut(je);
1269 u.copy_from(&tmp);
1270 let ref scale = u.norm_l2().recip();
1271 zip!(u).for_each(|unzip!(u)| {
1272 *u = u.mul_real(scale);
1273 });
1274 }
1275 }
1276}
1277
1278fn qz_to_gevd_real_scratch<T: RealField>(n: usize, _: Par) -> StackReq {
1279 StackReq::all_of(&[
1280 temp_mat_scratch::<T>(n, 1),
1281 temp_mat_scratch::<T>(n, 1),
1282 temp_mat_scratch::<T>(n, 2),
1283 temp_mat_scratch::<T>(2, 2),
1284 temp_mat_scratch::<T>(2, 2),
1285 StackReq::all_of(&[
1286 temp_mat_scratch::<T>(2, 2),
1287 temp_mat_scratch::<T>(n, 1),
1288 linalg::lu::full_pivoting::factor::lu_in_place_scratch::<
1289 usize,
1290 Complex<T>,
1291 >(2, 2, Par::Seq, Default::default()),
1292 linalg::lu::full_pivoting::solve::solve_in_place_scratch::<
1293 usize,
1294 Complex<T>,
1295 >(2, 1, Par::Seq),
1296 ]),
1297 temp_mat_scratch::<T>(n, 2),
1298 ])
1299}
1300
1301fn qz_to_gevd_cplx_scratch<T: ComplexField>(n: usize, _: Par) -> StackReq {
1302 StackReq::all_of(&[temp_mat_scratch::<T>(n, 1); 4])
1303}
1304
1305pub fn gevd_scratch<T: ComplexField>(
1308 dim: usize,
1309 left: ComputeEigenvectors,
1310 right: ComputeEigenvectors,
1311 par: Par,
1312 params: Spec<GevdParams, T>,
1313) -> StackReq {
1314 let _ = (left, right);
1315 let n = dim;
1316 let block_size =
1317 linalg::qr::no_pivoting::factor::recommended_block_size::<T>(n, n);
1318 StackReq::any_of(&[
1319 linalg::temp_mat_scratch::<T>(block_size, n).and(
1320 linalg::qr::no_pivoting::factor::qr_in_place_scratch::<T>(n, n, block_size, par, default())
1321 .or(linalg::householder::apply_block_householder_sequence_transpose_on_the_left_in_place_scratch::<T>(n, block_size, n)),
1322 ),
1323 gen_hessenberg::generalized_hessenberg_scratch::<T>(n, auto!(T)),
1324 if const { T::IS_REAL } {
1325 qz_real::hessenberg_to_qz_scratch::<T::Real>(n, par, params.schur)
1326 } else {
1327 qz_cplx::hessenberg_to_qz_scratch::<T>(n, par, params.schur)
1328 },
1329 if const { T::IS_REAL } {
1330 qz_to_gevd_real_scratch::<T::Real>(n, par)
1331 } else {
1332 qz_to_gevd_cplx_scratch::<T>(n, par)
1333 },
1334 ])
1335}
1336#[track_caller]
1343pub fn gevd_real<T: RealField>(
1344 A: MatMut<'_, T>,
1345 B: MatMut<'_, T>,
1346 S_re: DiagMut<'_, T>,
1347 S_im: DiagMut<'_, T>,
1348 beta: DiagMut<'_, T>,
1349 U_left: Option<MatMut<'_, T>>,
1350 U_right: Option<MatMut<'_, T>>,
1351 par: Par,
1352 stack: &mut MemStack,
1353 params: Spec<GevdParams, T>,
1354) -> Result<(), GevdError> {
1355 compute_gevd_generic(
1356 A,
1357 B,
1358 S_re.column_vector_mut(),
1359 S_im.column_vector_mut(),
1360 beta.column_vector_mut(),
1361 U_left,
1362 U_right,
1363 par,
1364 stack,
1365 params.config,
1366 qz_real::hessenberg_to_qz,
1367 qz_to_gevd_real,
1368 )
1369}
1370#[track_caller]
1377pub fn gevd_cplx<T: ComplexField>(
1378 A: MatMut<'_, T>,
1379 B: MatMut<'_, T>,
1380 S: DiagMut<'_, T>,
1381 beta: DiagMut<'_, T>,
1382 U_left: Option<MatMut<'_, T>>,
1383 U_right: Option<MatMut<'_, T>>,
1384 par: Par,
1385 stack: &mut MemStack,
1386 params: Spec<GevdParams, T>,
1387) -> Result<(), GevdError> {
1388 compute_gevd_generic(
1389 A,
1390 B,
1391 S.column_vector_mut(),
1392 ColMut::from_slice_mut(&mut []),
1393 beta.column_vector_mut(),
1394 U_left,
1395 U_right,
1396 par,
1397 stack,
1398 params.config,
1399 |A: MatMut<'_, T>,
1400 B: MatMut<'_, T>,
1401 Q: Option<MatMut<'_, T>>,
1402 Z: Option<MatMut<'_, T>>,
1403 alphar: ColMut<'_, T>,
1404 _: ColMut<'_, T>,
1405 beta: ColMut<'_, T>,
1406 eigenvectors: ComputeEigenvectors,
1407 par: Par,
1408 params: GeneralizedSchurParams,
1409 stack: &mut MemStack| {
1410 qz_cplx::hessenberg_to_qz(
1411 A,
1412 B,
1413 Q,
1414 Z,
1415 alphar,
1416 beta,
1417 eigenvectors,
1418 par,
1419 params,
1420 stack,
1421 )
1422 },
1423 qz_to_gevd_cplx,
1424 )
1425}
1426#[cfg(test)]
1427mod tests {
1428 use super::*;
1429 use crate::stats::prelude::*;
1430 use crate::utils;
1431 use dyn_stack::MemBuffer;
1432 use equator::assert;
1433 #[test]
1434 fn test_lishen_() {
1435 let approx_eq = utils::approx::CwiseMat(
1436 utils::approx::ApproxEq::<f64>::eps() * 128.0,
1437 );
1438 let A = &[
1439 [
1440 0.0000000067116330731078674,
1441 -0.0000000024189842394753674,
1442 0.00000000032505193899740187,
1443 0.0,
1444 0.0,
1445 0.0,
1446 ],
1447 [
1448 -0.0000000024189842394753674,
1449 0.000000011866543705551487,
1450 -0.00000001582083742901503,
1451 0.0,
1452 0.0,
1453 0.0,
1454 ],
1455 [
1456 0.00000000032505193899740187,
1457 -0.00000001582083742901503,
1458 0.00000002523087227632826,
1459 0.0,
1460 0.0,
1461 0.0,
1462 ],
1463 [0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
1464 [0.0, 0.0, 0.0, 0.0, 1.0, 0.0],
1465 [0.0, 0.0, 0.0, 0.0, 0.0, 1.0f64],
1466 ];
1467 let B = &[
1468 [
1469 0.00016038376001067668,
1470 -0.00003674235041182116,
1471 -0.0000029397921270058582,
1472 -1.0,
1473 -0.0,
1474 -0.0,
1475 ],
1476 [
1477 -0.00003674235041182116,
1478 0.0002038454538304322,
1479 -0.00021213416901900504,
1480 -0.0,
1481 -1.0,
1482 -0.0,
1483 ],
1484 [
1485 -0.0000029397921270058582,
1486 -0.00021213416901900504,
1487 0.0003954706173886255,
1488 -0.0,
1489 -0.0,
1490 -1.0,
1491 ],
1492 [1.0, 0.0, 0.0, 0.0, 0.0, 0.0],
1493 [0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
1494 [0.0, 0.0, 1.0, 0.0, 0.0, 0.0f64],
1495 ];
1496 let A = MatRef::from_row_major_array(A);
1497 let B = MatRef::from_row_major_array(B);
1498 let n = A.nrows();
1499 {
1500 let mut H = A.to_owned();
1501 let mut T = B.to_owned();
1502 let mut alpha_re = Diag::<f64>::zeros(n);
1503 let mut alpha_im = Diag::<f64>::zeros(n);
1504 let mut beta = Diag::<f64>::zeros(n);
1505 let mut UL = Mat::<f64>::identity(n, n);
1506 let mut UR = Mat::<f64>::identity(n, n);
1507 gevd_real(
1508 H.as_mut(),
1509 T.as_mut(),
1510 alpha_re.rb_mut(),
1511 alpha_im.rb_mut(),
1512 beta.rb_mut(),
1513 Some(UL.as_mut()),
1514 Some(UR.as_mut()),
1515 Par::Seq,
1516 MemStack::new(&mut MemBuffer::new(gevd_scratch::<f64>(
1517 n,
1518 ComputeEigenvectors::Yes,
1519 ComputeEigenvectors::Yes,
1520 Par::Seq,
1521 default(),
1522 ))),
1523 default(),
1524 )
1525 .unwrap();
1526 {
1527 let mut i = 0;
1528 while i < n {
1529 if alpha_im[i] == 0.0 {
1530 let u = UR.col(i);
1531 let a = alpha_re[i];
1532 let b = beta[i];
1533 assert!((b / a) * & A * u ~ B * u);
1534 i += 1;
1535 } else {
1536 let ur = UR.col(i);
1537 let ui = UR.col(i + 1);
1538 let ar = alpha_re[i];
1539 let ai = alpha_im[i];
1540 let b = beta[i];
1541 assert!(b * & A * ur ~ B * (ar * ur - ai * ui));
1542 assert!(b * & A * ui ~ B * (ar * ui + ai * ur));
1543 i += 2;
1544 }
1545 }
1546 }
1547 {
1548 let mut i = 0;
1549 while i < n {
1550 if alpha_im[i] == 0.0 {
1551 let u = UL.col(i);
1552 let a = alpha_re[i];
1553 let b = beta[i];
1554 assert!(b / a * u.adjoint() * & A ~ u.adjoint() * B);
1555 i += 1;
1556 } else {
1557 let ur = UL.col(i);
1558 let ui = UL.col(i + 1);
1559 let ar = alpha_re[i];
1560 let ai = alpha_im[i];
1561 let b = beta[i];
1562 assert!(
1563 b * ur.adjoint() * & A ~ (ar * ur - ai * ui).adjoint() * B
1564 );
1565 assert!(
1566 b * ui.adjoint() * & A ~ (ar * ui + ai * ur).adjoint() * B
1567 );
1568 i += 2;
1569 }
1570 }
1571 }
1572 }
1573 }
1574 #[test]
1575 fn test_cplx() {
1576 let rng = &mut StdRng::seed_from_u64(1);
1577 let approx_eq = utils::approx::CwiseMat(
1578 utils::approx::ApproxEq::<f64>::eps() * 128.0,
1579 );
1580 let n = 20;
1581 let A = &CwiseMatDistribution {
1582 nrows: n,
1583 ncols: n,
1584 dist: ComplexDistribution::new(StandardNormal, StandardNormal),
1585 }
1586 .rand::<Mat<c64>>(rng);
1587 let B = &CwiseMatDistribution {
1588 nrows: n,
1589 ncols: n,
1590 dist: ComplexDistribution::new(StandardNormal, StandardNormal),
1591 }
1592 .rand::<Mat<c64>>(rng);
1593 {
1594 let mut H = A.to_owned();
1595 let mut T = B.to_owned();
1596 let mut alpha_re = Diag::<c64>::zeros(n);
1597 let mut beta = Diag::<c64>::zeros(n);
1598 let mut UL = Mat::<c64>::identity(n, n);
1599 let mut UR = Mat::<c64>::identity(n, n);
1600 gevd_cplx(
1601 H.as_mut(),
1602 T.as_mut(),
1603 alpha_re.rb_mut(),
1604 beta.rb_mut(),
1605 Some(UL.as_mut()),
1606 Some(UR.as_mut()),
1607 Par::Seq,
1608 MemStack::new(&mut MemBuffer::new(gevd_scratch::<c64>(
1609 n,
1610 ComputeEigenvectors::Yes,
1611 ComputeEigenvectors::Yes,
1612 Par::Seq,
1613 default(),
1614 ))),
1615 default(),
1616 )
1617 .unwrap();
1618 {
1619 let mut i = 0;
1620 while i < n {
1621 let u = UR.col(i);
1622 let a = alpha_re[i];
1623 let b = beta[i];
1624 assert!(Scale(b / a) * A * u ~ B * u);
1625 i += 1;
1626 }
1627 }
1628 {
1629 let mut i = 0;
1630 while i < n {
1631 let u = UL.col(i);
1632 let a = alpha_re[i];
1633 let b = beta[i];
1634 assert!(Scale(b / a) * u.adjoint() * A ~ u.adjoint() * B);
1635 i += 1;
1636 }
1637 }
1638 }
1639 }
1640}
1641
1642#[cfg(test)]
1644mod t {
1645 use faer::dyn_stack::{MemBuffer, MemStack};
1646 use faer::linalg::evd::ComputeEigenvectors as CE;
1647 use faer::prelude::*;
1648 use faer::{Par, Spec, linalg};
1649
1650 fn mk(n: usize, seed: u64) -> Mat<f64> {
1651 let mut s = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
1652 let mut next = move || {
1653 s = s
1654 .wrapping_mul(6364136223846793005)
1655 .wrapping_add(1442695040888963407);
1656 ((s >> 33) as f64 / (1u64 << 31) as f64) - 1.0
1657 };
1658 Mat::from_fn(n, n, |i, j| next() + if i == j { n as f64 } else { 0.0 })
1659 }
1660
1661 fn gevd(a: &Mat<f64>, b: &Mat<f64>, vectors: bool) -> Vec<(f64, f64)> {
1663 let n = a.nrows();
1664 let (mut am, mut bm) = (a.clone(), b.clone());
1665 let mut sre = faer::diag::Diag::<f64>::zeros(n);
1666 let mut sim = faer::diag::Diag::<f64>::zeros(n);
1667 let mut bet = faer::diag::Diag::<f64>::zeros(n);
1668 let mut u = Mat::<f64>::zeros(n, n);
1669 let ce = if vectors { CE::Yes } else { CE::No };
1670 let mut mem = MemBuffer::new(linalg::gevd::gevd_scratch::<f64>(
1671 n,
1672 CE::No,
1673 ce,
1674 Par::Seq,
1675 Spec::default(),
1676 ));
1677 linalg::gevd::gevd_real(
1678 am.as_mut(),
1679 bm.as_mut(),
1680 sre.as_mut(),
1681 sim.as_mut(),
1682 bet.as_mut(),
1683 None,
1684 vectors.then(|| u.as_mut()),
1685 Par::Seq,
1686 MemStack::new(&mut mem),
1687 Spec::default(),
1688 )
1689 .unwrap();
1690 (0..n).map(|k| (sre[k] / bet[k], sim[k] / bet[k])).collect()
1691 }
1692
1693 fn residual(a: &Mat<f64>, b: &Mat<f64>, lam: (f64, f64)) -> f64 {
1695 let n = a.nrows();
1696 let mut m: Vec<(f64, f64)> = (0..n * n)
1697 .map(|k| {
1698 let (i, j) = (k % n, k / n);
1699 (a[(i, j)] - lam.0 * b[(i, j)], -lam.1 * b[(i, j)])
1700 })
1701 .collect();
1702 let mut det = (1.0f64, 0.0f64);
1703 for col in 0..n {
1704 let p = (col..n)
1705 .max_by(|&x, &y| {
1706 let f = |r: usize| m[r + col * n].0.hypot(m[r + col * n].1);
1707 f(x).partial_cmp(&f(y)).unwrap()
1708 })
1709 .unwrap();
1710 if p != col {
1711 for j in 0..n {
1712 m.swap(col + j * n, p + j * n);
1713 }
1714 det = (-det.0, -det.1);
1715 }
1716 let d = m[col + col * n];
1717 det = (det.0 * d.0 - det.1 * d.1, det.0 * d.1 + det.1 * d.0);
1718 let dn = d.0 * d.0 + d.1 * d.1;
1719 if dn == 0.0 {
1720 continue;
1721 }
1722 for r in col + 1..n {
1723 let x = m[r + col * n];
1724 let f = (
1725 (x.0 * d.0 + x.1 * d.1) / dn,
1726 (x.1 * d.0 - x.0 * d.1) / dn,
1727 );
1728 for j in col..n {
1729 let y = m[col + j * n];
1730 m[r + j * n].0 -= f.0 * y.0 - f.1 * y.1;
1731 m[r + j * n].1 -= f.0 * y.1 + f.1 * y.0;
1732 }
1733 }
1734 }
1735 det.0.hypot(det.1)
1736 }
1737
1738 #[test]
1748 fn eigenvalues_only_gives_wrong_complex_pairs() {
1749 let (mut bad_novec, mut bad_vec, mut total) = (0, 0, 0);
1750 for n in [3usize, 4, 5, 6, 8, 10, 12] {
1751 for seed in 0..40u64 {
1752 let a = mk(n, seed * 7919 + n as u64);
1753 let b = mk(n, seed * 7919 + n as u64 + 5000);
1754 let scale = (0..n * n)
1755 .map(|k| a[(k % n, k / n)].abs())
1756 .fold(1.0f64, f64::max);
1757 let tol = 1e-9 * scale.powi(n as i32);
1758 for (lams, vectors) in
1759 [(gevd(&a, &b, false), false), (gevd(&a, &b, true), true)]
1760 {
1761 for &l in &lams {
1762 if l.1 == 0.0 {
1763 continue;
1764 }
1765 if residual(&a, &b, l) > tol {
1766 if vectors {
1767 bad_vec += 1
1768 } else {
1769 bad_novec += 1
1770 }
1771 }
1772 }
1773 }
1774 total +=
1775 gevd(&a, &b, false).iter().filter(|l| l.1 != 0.0).count();
1776 }
1777 }
1778 assert_eq!(
1779 bad_novec, 0,
1780 "eigenvalues-only path is wrong ({bad_novec} of {total})"
1781 );
1782 assert_eq!(bad_vec, 0, "eigenvector path is wrong ({bad_vec})");
1783 }
1784
1785 #[test]
1788 fn gevd_scratch_is_too_small_for_n2() {
1789 let (mut panics, mut total) = (0, 0);
1790 for seed in 0..40u64 {
1791 let a = mk(2, seed * 7919 + 2);
1792 let b = mk(2, seed * 7919 + 2 + 5000);
1793 total += 1;
1794 if std::panic::catch_unwind(|| gevd(&a, &b, true)).is_err() {
1795 panics += 1;
1796 }
1797 }
1798 assert_eq!(
1799 panics, 0,
1800 "gevd_scratch under-allocates ({panics} of {total})"
1801 );
1802 }
1803}