Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
LookAheadLevinson.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9
10#ifndef EIGEN_STRUCTURED_LOOK_AHEAD_LEVINSON_H
11#define EIGEN_STRUCTURED_LOOK_AHEAD_LEVINSON_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17
18template <typename Scalar_>
20
21namespace internal {
22
23template <typename Scalar_>
24struct traits<LookAheadLevinson<Scalar_>> : traits<Matrix<Scalar_, Dynamic, Dynamic>> {
25 using XprKind = MatrixXpr;
26 using StorageKind = SolverStorage;
27 using StorageIndex = int;
28 using BaseTraits = traits<Matrix<Scalar_, Dynamic, Dynamic>>;
29 static constexpr int Flags = BaseTraits::Flags & RowMajorBit;
30 static constexpr int CoeffReadCost = Dynamic;
31};
32
33// Persymmetry E_n T_n E_n = T_n^T requires sum_i a_i b_i, not the conjugating dot().
34template <typename D1, typename D2>
35typename D1::Scalar structured_tdot(const MatrixBase<D1>& a, const MatrixBase<D2>& b) {
36 return a.cwiseProduct(b).sum();
37}
38
39template <typename Scalar>
40Matrix<Scalar, Dynamic, 1> structured_upshift(const Matrix<Scalar, Dynamic, 1>& v) {
41 const Index k = v.size();
42 Matrix<Scalar, Dynamic, 1> w = Matrix<Scalar, Dynamic, 1>::Zero(k);
43 if (k > 1) w.head(k - 1) = v.tail(k - 1);
44 return w;
45}
46
47} // namespace internal
48
86template <typename Scalar_>
87class LookAheadLevinson : public SolverBase<LookAheadLevinson<Scalar_>> {
88 public:
90 friend class SolverBase<LookAheadLevinson>;
91 EIGEN_GENERIC_PUBLIC_INTERFACE(LookAheadLevinson)
92 using DenseVector = Matrix<Scalar, Dynamic, 1>;
93 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
94
96 LookAheadLevinson() : m_maxBlockSize(4), m_n(0), m_isInitialized(false), m_info(InvalidInput) {}
97
100 template <int Rows_, int Cols_>
102 : m_maxBlockSize(4), m_n(0), m_isInitialized(false), m_info(InvalidInput) {
103 compute(T);
104 }
105
110 eigen_assert(p >= 1);
111 m_maxBlockSize = p;
112 return *this;
113 }
114
116 Index maxBlockSize() const { return m_maxBlockSize; }
117
118 Index rows() const noexcept { return m_n; }
119 Index cols() const noexcept { return m_n; }
120
122 template <int Rows_, int Cols_>
124
125#ifdef EIGEN_PARSED_BY_DOXYGEN
131 template <typename Rhs>
133#endif
134
135#ifndef EIGEN_PARSED_BY_DOXYGEN
143 template <typename RhsType, typename DstType>
144 void _solve_impl(const RhsType& rhs, DstType& dst) const {
145 dst.noalias() = solveForward(rhs);
146 }
147
152 template <bool Conjugate, typename RhsType, typename DstType>
153 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const {
154 const DenseMatrix reversed = rhs.template conjugateIf<Conjugate>().colwise().reverse();
155 dst = solveForward(reversed).colwise().reverse().template conjugateIf<Conjugate>();
156 }
157#endif
158
163 eigen_assert(m_isInitialized && "LookAheadLevinson is not initialized.");
164 return m_info;
165 }
166
169 RealScalar conditionEstimate() const {
170 eigen_assert(m_isInitialized && "LookAheadLevinson is not initialized.");
171 return m_sMin > RealScalar(0) ? m_normEst / m_sMin : NumTraits<RealScalar>::infinity();
172 }
173
174 private:
177 template <typename Rhs>
178 DenseMatrix solveForward(const Rhs& b) const {
179 const Index nrhs = b.cols();
180 DenseMatrix x = m_luInit.solve(b.topRows(m_k0));
181 DenseMatrix rhs, a, xn;
182 for (const Step& s : m_steps) {
183 rhs.noalias() = b.middleRows(s.k, s.p) - s.WspEk * x; // (27): b_p - S_p^T E_k x_k
184 a = s.luGamma.solve(rhs);
185 xn.resize(s.k + s.p, nrhs);
186 xn.topRows(s.k).noalias() = x + s.EkYp * a; // [E_k Y_p; I_p] a_p
187 xn.bottomRows(s.p) = a;
188 x = xn;
189 }
190 return x;
191 }
192
193 // Per accepted block step, the b-independent data needed to advance x in solve().
194 struct Step {
195 Index k; // order before the step
196 Index p; // block size
197 DenseMatrix EkYp; // E_k Y_p (k x p)
198 DenseMatrix WspEk; // S_p^T E_k (p x k)
199 FullPivLU<DenseMatrix> luGamma;
200 };
201
202 // Leading p x p principal submatrix built directly from the generators.
203 static DenseMatrix leadingBlock(const DenseVector& c, const DenseVector& r, Index p) {
204 DenseMatrix B(p, p);
205 for (Index j = 0; j < p; ++j) {
206 B.col(j).head(j) = r.segment(1, j).reverse();
207 B.col(j).tail(p - j) = c.head(p - j);
208 }
209 return B;
210 }
211
212 // Builds a (len x cols) block whose column j is the length-len generator segment
213 // v.segment(first + j, len); used to assemble the S_p and R_p shift blocks.
214 static DenseMatrix shiftBlock(const DenseVector& v, Index first, Index len, Index cols) {
215 DenseMatrix B(len, cols);
216 for (Index j = 0; j < cols; ++j) B.col(j) = v.segment(first + j, len);
217 return B;
218 }
219
220 static RealScalar smallestSingularValue(const DenseMatrix& M) {
221 if (M.rows() == 1) return numext::abs(M(0, 0));
222 JacobiSVD<DenseMatrix> svd(M);
223 return svd.singularValues()(svd.singularValues().size() - 1);
224 }
225
226 Index m_maxBlockSize;
227 Index m_n;
228 Index m_k0;
229 FullPivLU<DenseMatrix> m_luInit; // LU of the leading T_{k0}
230 std::vector<Step> m_steps;
231 bool m_isInitialized;
232 ComputationInfo m_info;
233 RealScalar m_sMin;
234 RealScalar m_normEst;
235};
236
237template <typename Scalar_>
238template <int Rows_, int Cols_>
240 using internal::structured_tdot;
241 using internal::structured_upshift;
242
243 EIGEN_INTERNAL_CHECK_SHAPE(T.rows() == T.cols() && "LookAheadLevinson requires a square Toeplitz matrix",
244 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES,
245 internal::square_dimensions<Toeplitz<Scalar, Rows_, Cols_>>);
246 const Index n = T.rows();
247 const DenseVector& c = T.column(); // (rho_0, sigma_1, ..., sigma_{n-1})
248 const DenseVector& r = T.row(); // (rho_0, rho_1, ..., rho_{n-1})
249 const Scalar rho0 = c[0];
250
251 m_n = n;
252 m_steps.clear();
253 m_info = Success;
254 m_normEst = c.cwiseAbs().sum() + r.cwiseAbs().sum(); // cheap upper bound on ||T||_2
255
256 Index k;
257 DenseVector y, z;
258 Scalar gamma(0);
259 {
260 Index kbest = 1;
261 RealScalar best = RealScalar(-1);
262 const Index kmax = numext::mini<Index>(m_maxBlockSize, n);
263 for (Index i = 1; i <= kmax; ++i) {
264 RealScalar sv = smallestSingularValue(leadingBlock(c, r, i));
265 if (sv > best) {
266 best = sv;
267 kbest = i;
268 }
269 }
270 k = m_k0 = kbest;
271 m_luInit.compute(leadingBlock(c, r, k));
272 m_sMin = best;
273 }
274
275 bool lastWasBlock = false;
276 DenseVector yPrev, zPrev;
277 Scalar gammaPrev(0);
278 Index kp = 0, pp = 0;
279 DenseMatrix Ypp, Zpp;
280 FullPivLU<DenseMatrix> luGammaPP;
281 DenseVector y_kp_1, z_kp_1;
282
283 if (k < n) {
284 y = m_luInit.transpose().solve((-r.segment(1, k)).eval()); // T_k^T y = -r_k
285 z = m_luInit.solve((-c.segment(1, k)).eval()); // T_k z = -s_k
286 gamma = rho0 + structured_tdot(c.segment(1, k), y);
287 if (k == 1) {
288 lastWasBlock = false;
289 yPrev = DenseVector::Zero(0);
290 zPrev = DenseVector::Zero(0);
291 gammaPrev = rho0; // gamma^{(0)}
292 } else {
293 lastWasBlock = true; // treat init as a block step of size k from order 0
294 kp = 0;
295 pp = k;
296 Ypp = DenseMatrix::Zero(0, k);
297 Zpp = DenseMatrix::Zero(0, k);
298 luGammaPP = m_luInit;
299 y_kp_1 = DenseVector::Zero(0);
300 z_kp_1 = DenseVector::Zero(0);
301 }
302 }
303
304 while (k < n) {
305 const Index pcap = numext::mini<Index>(m_maxBlockSize, n - k);
306 const DenseVector Ek_y = y.reverse(), Ek_z = z.reverse();
307
308 DenseVector g_k, h_k;
309 bool gh_ready = false;
310 auto ensure_gh = [&]() {
311 if (gh_ready) return;
312 if (!lastWasBlock) {
313 // Theorem 1, eq (33)
314 g_k.resize(k);
315 h_k.resize(k);
316 g_k.head(k - 1) = zPrev.reverse();
317 g_k[k - 1] = Scalar(1);
318 g_k /= gammaPrev;
319 h_k.head(k - 1) = yPrev.reverse();
320 h_k[k - 1] = Scalar(1);
321 h_k /= gammaPrev;
322 } else {
323 // Theorem 2: y_{k,1}, z_{k,1} (eqs 47-49), then g_k, h_k (eq 50).
324 DenseVector rhs_y = -r.segment(kp + 2, pp);
325 DenseVector rhs_z = -c.segment(kp + 2, pp);
326 if (kp > 0) {
327 const DenseMatrix Rpp = shiftBlock(r, 1, kp, pp);
328 const DenseMatrix Spp = shiftBlock(c, 1, kp, pp);
329 rhs_y.noalias() -= Rpp.transpose() * y_kp_1.reverse();
330 rhs_z.noalias() -= Spp.transpose() * z_kp_1.reverse();
331 }
332 const DenseVector a_y = luGammaPP.transpose().solve(rhs_y);
333 const DenseVector a_z = luGammaPP.solve(rhs_z);
334 DenseVector yk1 = DenseVector::Zero(k), zk1 = DenseVector::Zero(k);
335 if (kp > 0) {
336 yk1.head(kp) = y_kp_1 + (Zpp * a_y).reverse();
337 zk1.head(kp) = z_kp_1 + (Ypp * a_z).reverse();
338 }
339 yk1.tail(pp) = a_y;
340 zk1.tail(pp) = a_z;
341 const Scalar c1 = -r[k + 1] - structured_tdot(r.segment(1, k), Ek_y);
342 const Scalar d1 = -c[k + 1] - structured_tdot(c.segment(1, k), Ek_z);
343 g_k = (yk1 - structured_upshift<Scalar>(y) + y[0] * y) / c1;
344 h_k = (zk1 - structured_upshift<Scalar>(z) + z[0] * z) / d1;
345 }
346 gh_ready = true;
347 };
348
349 // Build Y_p, Z_p incrementally and pick the block size p (eqs 31-32, 46, 39).
350 DenseMatrix Yp(k, pcap), Zp(k, pcap);
351 Yp.col(0) = y;
352 Zp.col(0) = z;
353 Index chosen = -1;
354 Index bestP = 1;
355 RealScalar bestPsi = RealScalar(-1);
356 DenseMatrix bestGamma;
357
358 for (Index p = 1; p <= pcap; ++p) {
359 if (p >= 2) {
360 ensure_gh();
361 const Index i = p - 1;
362 const Scalar ci = -r[k + i] - structured_tdot(r.segment(i, k), Ek_y);
363 const Scalar di = -c[k + i] - structured_tdot(c.segment(i, k), Ek_z);
364 Yp.col(i) = structured_upshift<Scalar>(Yp.col(i - 1)) - Yp.col(i - 1)[0] * y + ci * g_k;
365 Zp.col(i) = structured_upshift<Scalar>(Zp.col(i - 1)) - Zp.col(i - 1)[0] * z + di * h_k;
366 }
367 const DenseMatrix Sp = shiftBlock(c, 1, k, p);
368 DenseMatrix Gamma = leadingBlock(c, r, p) + Sp.transpose() * Yp.leftCols(p); // (20)
369 const RealScalar muY = Yp.leftCols(p).cwiseAbs().maxCoeff();
370 const RealScalar muZ = Zp.leftCols(p).cwiseAbs().maxCoeff();
371 const RealScalar denom = numext::maxi(numext::maxi(RealScalar(1), muY), numext::maxi(muZ, muY * muZ));
372 const RealScalar psi = smallestSingularValue(Gamma) / denom; // (46)
373 if (psi > bestPsi) {
374 bestPsi = psi;
375 bestP = p;
376 bestGamma = Gamma;
377 }
378 if (psi > RealScalar(0.1) * m_sMin) { // (39)
379 chosen = p;
380 bestGamma = Gamma;
381 break;
382 }
383 }
384
385 DenseMatrix Gamma = bestGamma;
386 Index p;
387 if (chosen > 0) {
388 p = chosen;
389 } else {
390 p = bestP;
391 m_sMin = bestPsi; // pmax too small to skip cleanly; record the degraded conditioning
392 }
393
394 const Index K = k + p;
395 const bool finalStep = (K == n);
396
397 const DenseMatrix Sp = shiftBlock(c, 1, k, p);
398 const DenseMatrix Rp = shiftBlock(r, 1, k, p);
399 FullPivLU<DenseMatrix> luG(Gamma);
400
401 // Record the b-independent data for solve(): rhs = b_p - (S_p^T E_k) x_k ; x update via E_k Y_p.
402 Step step;
403 step.k = k;
404 step.p = p;
405 step.EkYp = Yp.leftCols(p).colwise().reverse(); // E_k Y_p
406 step.WspEk = Sp.transpose().rowwise().reverse(); // S_p^T E_k
407 step.luGamma = luG;
408 m_steps.push_back(step);
409
410 if (!finalStep) {
411 const DenseVector rhs_e = -r.segment(k + 1, p) - Rp.transpose() * Ek_y; // (28)
412 const DenseVector rhs_f = -c.segment(k + 1, p) - Sp.transpose() * Ek_z; // (29)
413 const DenseVector e_p = luG.transpose().solve(rhs_e);
414 const DenseVector f_p = luG.solve(rhs_f);
415
416 DenseVector y_new(K), z_new(K);
417 y_new.head(k) = y + (Zp.leftCols(p) * e_p).reverse(); // (25)
418 y_new.tail(p) = e_p;
419 z_new.head(k) = z + (Yp.leftCols(p) * f_p).reverse(); // (26)
420 z_new.tail(p) = f_p;
421
422 const DenseVector y_save = y, z_save = z;
423 const Scalar gamma_save = gamma;
424 if (p == 1)
425 gamma = (Scalar(1) - e_p[0] * f_p[0]) * gamma; // (15)
426 else
427 gamma = rho0 + structured_tdot(c.segment(1, K), y_new); // (5)
428 y = y_new;
429 z = z_new;
430
431 if (p == 1) {
432 lastWasBlock = false;
433 yPrev = y_save;
434 zPrev = z_save;
435 gammaPrev = gamma_save;
436 } else {
437 lastWasBlock = true;
438 kp = k;
439 pp = p;
440 Ypp = Yp.leftCols(p);
441 Zpp = Zp.leftCols(p);
442 luGammaPP = luG;
443 y_kp_1 = Yp.col(1);
444 z_kp_1 = Zp.col(1);
445 }
446 }
447 k = K;
448 }
449
450 const RealScalar kappa = m_sMin > RealScalar(0) ? m_normEst / m_sMin : NumTraits<RealScalar>::infinity();
451 if (!(kappa * NumTraits<RealScalar>::epsilon() < RealScalar(1))) m_info = NumericalIssue;
452 m_isInitialized = true;
453 return *this;
454}
455
456} // namespace Eigen
457
458#endif // EIGEN_STRUCTURED_LOOK_AHEAD_LEVINSON_H
Look-ahead Levinson direct solver for general Toeplitz systems.
Definition LookAheadLevinson.h:87
ComputationInfo info() const
Definition LookAheadLevinson.h:162
LookAheadLevinson(const Toeplitz< Scalar, Rows_, Cols_ > &T)
Definition LookAheadLevinson.h:101
LookAheadLevinson()
Definition LookAheadLevinson.h:96
LookAheadLevinson & setMaxBlockSize(Index p)
Definition LookAheadLevinson.h:109
Index maxBlockSize() const
Definition LookAheadLevinson.h:116
RealScalar conditionEstimate() const
Definition LookAheadLevinson.h:169
LookAheadLevinson & compute(const Toeplitz< Scalar, Rows_, Cols_ > &T)
const Solve< LookAheadLevinson, Rhs > solve(const MatrixBase< Rhs > &b) const
An m x n Toeplitz matrix represented by its first column and row.
Definition Toeplitz.h:85
ComputationInfo
NumericalIssue
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.
constexpr Index size() const noexcept