148 const VectorType& z,
int options) {
149 const Index n = d.size();
150 EIGEN_INTERNAL_ASSERT_SAME_SIZE_MSG(d, z,
"d and z must have the same size");
151 eigen_assert((options & ~EigVecMask) == 0 && (options & EigVecMask) != EigVecMask &&
"invalid option parameter");
153 m_vectorsComputed =
false;
156 m_eivalues.resize(n);
157 if (computeVectors) m_eivec.setIdentity(n, n);
161 if (!(d.allFinite() && z.allFinite() && (numext::isfinite)(rho))) {
164 m_isInitialized =
true;
168 m_vectorsComputed = computeVectors;
169 m_isInitialized =
true;
173 const bool negated = rho < RealScalar(0);
174 const VectorType dW = negated ? VectorType(-d) : d;
177 std::vector<Index> pi;
178 pi.reserve(
static_cast<std::size_t
>(n));
179 for (Index i = 0; i < n; ++i) pi.push_back(i);
180 std::stable_sort(pi.begin(), pi.end(), [&dW](Index a, Index b) { return dW[a] < dW[b]; });
181 VectorType ds(n), zs(n);
182 for (Index i = 0; i < n; ++i) {
183 ds[i] = dW[pi[
static_cast<std::size_t
>(i)]];
184 zs[i] = z[pi[
static_cast<std::size_t
>(i)]];
190 const RealScalar znorm = zs.stableNorm();
191 if (znorm > RealScalar(0)) zs /= znorm;
192 RealScalar rhoW = rho == RealScalar(0) || znorm == RealScalar(0) ? RealScalar(0) : (numext::abs(rho) * znorm) * znorm;
193 if (!(numext::isfinite)(rhoW)) {
198 m_isInitialized =
true;
201 EIGEN_USING_STD(frexp)
202 EIGEN_USING_STD(ldexp)
203 RealScalar scaledNorm = numext::maxi(ds.cwiseAbs().maxCoeff(), rhoW);
205 if (scaledNorm > RealScalar(0)) scaledNorm = frexp(scaledNorm, &scaleExp);
206 ds = ds.array().ldexp(-scaleExp).matrix();
207 rhoW = ldexp(rhoW, -scaleExp);
216 std::vector<Rotation> rotations;
217 std::vector<bool> deflated;
220 deflated.assign(
static_cast<std::size_t
>(n),
true);
223 deflated.reserve(
static_cast<std::size_t
>(n));
224 for (Index i = 0; i < n; ++i) deflated.push_back(rhoW * numext::abs(zs[i]) <= tol);
227 for (Index i = 0; i < n; ++i) {
228 if (deflated[
static_cast<std::size_t
>(i)])
continue;
230 const RealScalar r = numext::hypot(zs[p], zs[i]);
231 const RealScalar c = zs[i] / r, s = zs[p] / r;
232 const RealScalar gap = ds[i] - ds[p];
233 if (numext::abs(c * s * gap) <= tol) {
239 const RealScalar left = ds[p], right = ds[i];
240 if (numext::abs(s) <= numext::abs(c)) {
241 const RealScalar shift = s * s * gap;
242 ds[p] = left + shift;
243 ds[i] = right - shift;
245 const RealScalar shift = c * c * gap;
246 ds[p] = right - shift;
247 ds[i] = left + shift;
250 zs[p] = RealScalar(0);
251 deflated[
static_cast<std::size_t
>(p)] =
true;
255 rotations.push_back(Rotation{p, i, c, s});
258 if (!deflated[
static_cast<std::size_t
>(i)]) p = i;
262 std::vector<Index> sub;
263 for (Index i = 0; i < n; ++i)
264 if (!deflated[
static_cast<std::size_t
>(i)]) sub.push_back(i);
265 const Index m =
static_cast<Index
>(sub.size());
267 VectorType lambdaW = ds;
269 MatrixType subVectors;
272 VectorType delta(m),
zeta(m), zeta2(m);
273 std::vector<Index> shiftIndex(
static_cast<std::size_t
>(m));
275 for (Index a = 0; a < m; ++a) {
276 delta[a] = ds[sub[
static_cast<std::size_t
>(a)]];
277 zeta[a] = zs[sub[
static_cast<std::size_t
>(a)]];
279 zeta2.array() =
zeta.array() *
zeta.array();
280 const RealScalar zeta2sum = zeta2.sum();
286 (std::numeric_limits<RealScalar>::digits > 0) ?
static_cast<int>(std::numeric_limits<RealScalar>::digits) : 128;
287 const int expRange = (std::numeric_limits<RealScalar>::max_exponent > std::numeric_limits<RealScalar>::min_exponent)
288 ?
static_cast<int>(std::numeric_limits<RealScalar>::max_exponent) -
289 static_cast<int>(std::numeric_limits<RealScalar>::min_exponent)
291 const int maxBisect = expRange + 2 * digits + 32;
292 VectorType lam(m), dsh(m);
293 for (Index k = 0; k < m; ++k) {
302 hi = rhoW * zeta2sum;
306 const RealScalar left = delta[k], right = delta[k + 1];
307 const RealScalar mid = left + (right - left) / RealScalar(2);
308 if (secular(delta, zeta2, rhoW, mid) > RealScalar(0)) {
318 const RealScalar shiftVal = delta[shift];
319 dsh.array() = delta.array() - shiftVal;
324 RealScalar a0 = lo, b0 = hi;
325 bool converged =
false;
326 for (
int iter = 0; iter < maxBisect; ++iter) {
327 const RealScalar t = a0 + (b0 - a0) / RealScalar(2);
328 if (t == a0 || t == b0) {
332 if (secular(dsh, zeta2, rhoW, t) > RealScalar(0))
338 const RealScalar t = a0 + (b0 - a0) / RealScalar(2);
339 shiftIndex[
static_cast<std::size_t
>(k)] = shift;
341 lam[k] = shiftVal + t;
349 for (Index i = 0; i < m; ++i) {
350 RealScalar acc = ((delta[shiftIndex[
static_cast<std::size_t
>(i)]] - delta[i]) + tau[i]) / rhoW;
351 for (Index j = 0; j < m; ++j) {
352 if (j == i)
continue;
353 const RealScalar num = (delta[shiftIndex[
static_cast<std::size_t
>(j)]] - delta[i]) + tau[j];
354 acc *= num / (delta[j] - delta[i]);
356 zhat[i] = numext::abs(acc) > RealScalar(0) ? RealScalar(numext::sqrt(numext::abs(acc))) : RealScalar(0);
357 if (
zeta[i] < RealScalar(0)) zhat[i] = -zhat[i];
361 if (computeVectors) {
363 for (Index j = 0; j < m; ++j) {
364 const Index sj = shiftIndex[
static_cast<std::size_t
>(j)];
365 if (tau[j] == RealScalar(0)) {
369 subVectors(sj, j) = RealScalar(1);
374 subVectors.col(j).array() = zhat.array() / ((delta.array() - delta[sj]) - tau[j]);
375 subVectors.col(j).stableNormalize();
378 for (Index k = 0; k < m; ++k) lambdaW[sub[static_cast<std::size_t>(k)]] = lam[k];
381 std::vector<Index> order;
382 order.reserve(
static_cast<std::size_t
>(n));
383 for (Index i = 0; i < n; ++i) order.push_back(i);
384 std::stable_sort(order.begin(), order.end(), [&lambdaW](Index a, Index b) { return lambdaW[a] < lambdaW[b]; });
386 std::vector<Index> subSlot(
static_cast<std::size_t
>(n), -1);
387 for (Index a = 0; a < m; ++a) subSlot[static_cast<std::size_t>(sub[
static_cast<std::size_t
>(a)])] = a;
389 for (Index t = 0; t < n; ++t) {
390 const Index w = order[
static_cast<std::size_t
>(t)];
391 const Index outCol = negated ? n - 1 - t : t;
392 m_eivalues[outCol] = negated ? -lambdaW[w] : lambdaW[w];
393 if (!computeVectors)
continue;
395 VectorType wvec = VectorType::Zero(n);
396 const Index slot = subSlot[
static_cast<std::size_t
>(w)];
398 wvec[w] = RealScalar(1);
400 for (Index a = 0; a < m; ++a) wvec[sub[static_cast<std::size_t>(a)]] = subVectors(a, slot);
405 for (
auto it = rotations.rbegin(); it != rotations.rend(); ++it) {
406 const RealScalar wi = wvec[it->i], wj = wvec[it->j];
407 wvec[it->i] = it->c * wi + it->s * wj;
408 wvec[it->j] = -it->s * wi + it->c * wj;
410 for (Index i = 0; i < n; ++i) m_eivec(pi[static_cast<std::size_t>(i)], outCol) = wvec[i];
413 m_eivalues = m_eivalues.array().ldexp(scaleExp).matrix();
414 if (!m_eivalues.allFinite()) {
415 m_eivalues.setConstant(NumTraits<RealScalar>::quiet_NaN());
416 m_info = InvalidInput;
419 m_vectorsComputed = computeVectors && m_info !=
InvalidInput;
420 m_isInitialized =
true;