Skip to main content

faer/linalg/gevd/
mod.rs

1//! low level implementation of the generalized eigenvalue decomposition of a
2//! square matrix pair.
3//!
4//! the generalized eigenvalue decomposition of a matrix pair $(A, B)$ of shape
5//! $(n, n)$ is a decomposition into components $S$, $U$ such that:
6//!
7//! - $U$ has shape $(n, n)$ and is invertible
8//! - $S$ has shape $(n, n)$ and is a diagonal matrix
9//! - and finally:
10//!
11//! $$A = B U S U^{-1}$$
12//!
13//! if $A$ is self-adjoint and $B$ is positive definite, then $U$ can be made
14//! unitary ($U^{-1} = U^H$), and $S$ is real valued.
15//!
16//! the implementation can choose to compute the left and/or right generalized
17//! eigenvectors separately, and the generalized eigenvalues (diagonal of $S$)
18//! are represented as a ratio $\alpha / \beta$ to improve numerical stability.
19use crate::internal_prelude::*;
20use complex::Complex;
21use equator::assert;
22pub use linalg::evd::ComputeEigenvectors;
23/// eigendecomposition error
24#[derive(Copy, Clone, Debug, PartialEq, Eq)]
25pub enum GevdError {
26	/// reached max iterations
27	NoConvergence,
28}
29/// eigendecomposition error
30#[derive(Copy, Clone, Debug, PartialEq, Eq)]
31pub enum SelfAdjointGevdError {
32	/// reached max iterations
33	NoConvergence,
34	/// B matrix not positive definite
35	NonPositiveDefinite,
36}
37/// generalized schur decomposition parameters
38#[derive(Clone, Copy, Debug)]
39pub struct GeneralizedSchurParams {
40	/// An estimate of the relative cost of flops within the near-the-diagonal
41	/// shift chase compared to flops within the matmul calls of a QZ sweep.
42	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	/// Function that returns the number of shifts to use for a given matrix
48	/// size
49	pub recommended_shift_count: extern "C" fn(
50		matrix_dimension: usize,
51		active_block_dimension: usize,
52	) -> usize,
53	/// Function that returns the deflation window to use for a given matrix
54	/// size
55	pub recommended_deflation_window: extern "C" fn(
56		matrix_dimension: usize,
57		active_block_dimension: usize,
58	) -> usize,
59	/// Threshold to switch between blocked and unblocked code
60	pub blocking_threshold: usize,
61	/// Threshold of percent of aggressive-early-deflation window that must
62	/// converge to skip a sweep
63	pub nibble_threshold: usize,
64	#[doc(hidden)]
65	pub non_exhaustive: NonExhaustive,
66}
67/// schur to eigendecomposition conversion parameters
68#[derive(Clone, Copy, Debug)]
69pub struct GevdFromSchurParams {
70	#[doc(hidden)]
71	pub non_exhaustive: NonExhaustive,
72}
73/// eigendecomposition tuning parameters
74#[derive(Clone, Copy, Debug)]
75pub struct GevdParams {
76	/// hessenberg parameters
77	pub hessenberg: gen_hessenberg::GeneralizedHessenbergParams,
78	/// schur from hessenberg conversion parameters
79	pub schur: GeneralizedSchurParams,
80	/// eigendecomposition from schur conversion parameters
81	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}
123/// hessenberg decomposition
124pub mod gen_hessenberg;
125/// $QZ$ decomposition for complex matrices
126pub mod qz_cplx;
127/// $QZ$ decomposition for real matrices
128pub 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	// the qz iteration reports a breakdown (a non-finite iterate) through
312	// non-finite eigenvalues. a genuine infinite eigenvalue has `beta = 0` with
313	// finite `alpha`, so it is not mistaken for one
314	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
1305/// computes the layout of the workspace required to compute a matrix pair's
1306/// generalized eigendecomposition
1307pub 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/// computes the real matrix pair $(A, B)$'s eigendecomposition
1337///
1338/// the eigenvalues are stored in $S$, the left eigenvectors in $U_L$, and the
1339/// right eigenvectors in $U_R$
1340///
1341/// the values in $A$ and $B$ after this function is called are unspecified.
1342#[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/// computes the complex matrix pair $(A, B)$'s eigendecomposition
1371///
1372/// the eigenvalues are stored in $S$, the left eigenvectors in $U_L$, and the
1373/// right eigenvectors in $U_R$
1374///
1375/// the values in $A$ and $B$ after this function is called are unspecified.
1376#[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// tests by @sjoelund
1643#[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	/// `gevd_real`, with the right-eigenvector flag as a parameter.
1662	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	/// |det(A - lambda B)|, zero exactly at an eigenvalue.
1694	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	/// ISSUE 1 (documentation): `gevd_real` writes a complex conjugate pair's
1739	/// eigenvalue into the FIRST slot only. The second slot holds the 2x2
1740	/// block's other diagonal entry, which is not an eigenvalue -- reading it
1741	/// gives a value whose `det(A - lambda B)` is O(1e-2) rather than O(1e-16).
1742	///
1743	/// faer's own `Solvers` layer never reads it: `solvers.rs::real_to_cplx`
1744	/// builds `S[j + 1]` from `S_re[j]`, not `S_re[j + 1]`. Nothing on
1745	/// `gevd_real` says so, and the same applies to
1746	/// `qz_real::hessenberg_to_qz`.
1747	#[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	/// BUG 2: `gevd_scratch` under-allocates, so `gevd_real` panics inside
1786	/// `temp_mat_zeroed`. n = 2 with eigenvectors requested.
1787	#[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}