10#ifndef EIGEN_STRUCTURED_LOOK_AHEAD_LEVINSON_H
11#define EIGEN_STRUCTURED_LOOK_AHEAD_LEVINSON_H
14#include "./InternalHeaderCheck.h"
18template <
typename Scalar_>
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;
34template <
typename D1,
typename D2>
35typename D1::Scalar structured_tdot(
const MatrixBase<D1>& a,
const MatrixBase<D2>& b) {
36 return a.cwiseProduct(b).sum();
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);
86template <
typename Scalar_>
100 template <
int Rows_,
int Cols_>
102 : m_maxBlockSize(4), m_n(0), m_isInitialized(false), m_info(
InvalidInput) {
110 eigen_assert(p >= 1);
118 Index rows() const noexcept {
return m_n; }
119 Index cols() const noexcept {
return m_n; }
122 template <
int Rows_,
int Cols_>
125#ifdef EIGEN_PARSED_BY_DOXYGEN
131 template <
typename Rhs>
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);
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>();
163 eigen_assert(m_isInitialized &&
"LookAheadLevinson is not initialized.");
170 eigen_assert(m_isInitialized &&
"LookAheadLevinson is not initialized.");
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;
184 a = s.luGamma.solve(rhs);
185 xn.resize(s.k + s.p, nrhs);
186 xn.topRows(s.k).noalias() = x + s.EkYp * a;
187 xn.bottomRows(s.p) = a;
199 FullPivLU<DenseMatrix> luGamma;
203 static DenseMatrix leadingBlock(
const DenseVector& c,
const DenseVector& r,
Index 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);
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);
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);
226 Index m_maxBlockSize;
229 FullPivLU<DenseMatrix> m_luInit;
230 std::vector<Step> m_steps;
231 bool m_isInitialized;
234 RealScalar m_normEst;
237template <
typename Scalar_>
238template <
int Rows_,
int Cols_>
240 using internal::structured_tdot;
241 using internal::structured_upshift;
243 EIGEN_INTERNAL_CHECK_SHAPE(T.rows() == T.cols() &&
"LookAheadLevinson requires a square Toeplitz matrix",
244 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES,
246 const Index n = T.rows();
247 const DenseVector& c = T.column();
248 const DenseVector& r = T.row();
249 const Scalar rho0 = c[0];
254 m_normEst = c.cwiseAbs().sum() + r.cwiseAbs().sum();
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));
271 m_luInit.compute(leadingBlock(c, r, k));
275 bool lastWasBlock =
false;
276 DenseVector yPrev, zPrev;
278 Index kp = 0, pp = 0;
279 DenseMatrix Ypp, Zpp;
281 DenseVector y_kp_1, z_kp_1;
284 y = m_luInit.transpose().solve((-r.segment(1, k)).eval());
285 z = m_luInit.solve((-c.segment(1, k)).eval());
286 gamma = rho0 + structured_tdot(c.segment(1, k), y);
288 lastWasBlock =
false;
289 yPrev = DenseVector::Zero(0);
290 zPrev = DenseVector::Zero(0);
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);
305 const Index pcap = numext::mini<Index>(m_maxBlockSize, n - k);
306 const DenseVector Ek_y = y.reverse(), Ek_z = z.reverse();
308 DenseVector g_k, h_k;
309 bool gh_ready =
false;
310 auto ensure_gh = [&]() {
311 if (gh_ready)
return;
316 g_k.head(k - 1) = zPrev.reverse();
317 g_k[k - 1] = Scalar(1);
319 h_k.head(k - 1) = yPrev.reverse();
320 h_k[k - 1] = Scalar(1);
324 DenseVector rhs_y = -r.segment(kp + 2, pp);
325 DenseVector rhs_z = -c.segment(kp + 2, pp);
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();
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);
336 yk1.head(kp) = y_kp_1 + (Zpp * a_y).reverse();
337 zk1.head(kp) = z_kp_1 + (Ypp * a_z).reverse();
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;
350 DenseMatrix Yp(k, pcap), Zp(k, pcap);
355 RealScalar bestPsi = RealScalar(-1);
356 DenseMatrix bestGamma;
358 for (Index p = 1; p <= pcap; ++p) {
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;
367 const DenseMatrix Sp = shiftBlock(c, 1, k, p);
368 DenseMatrix Gamma = leadingBlock(c, r, p) + Sp.transpose() * Yp.leftCols(p);
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;
378 if (psi > RealScalar(0.1) * m_sMin) {
385 DenseMatrix Gamma = bestGamma;
394 const Index K = k + p;
395 const bool finalStep = (K == n);
397 const DenseMatrix Sp = shiftBlock(c, 1, k, p);
398 const DenseMatrix Rp = shiftBlock(r, 1, k, p);
405 step.EkYp = Yp.leftCols(p).colwise().reverse();
406 step.WspEk = Sp.transpose().rowwise().reverse();
408 m_steps.push_back(step);
411 const DenseVector rhs_e = -r.segment(k + 1, p) - Rp.transpose() * Ek_y;
412 const DenseVector rhs_f = -c.segment(k + 1, p) - Sp.transpose() * Ek_z;
413 const DenseVector e_p = luG.transpose().solve(rhs_e);
414 const DenseVector f_p = luG.solve(rhs_f);
416 DenseVector y_new(K), z_new(K);
417 y_new.head(k) = y + (Zp.leftCols(p) * e_p).reverse();
419 z_new.head(k) = z + (Yp.leftCols(p) * f_p).reverse();
422 const DenseVector y_save = y, z_save = z;
423 const Scalar gamma_save = gamma;
425 gamma = (Scalar(1) - e_p[0] * f_p[0]) * gamma;
427 gamma = rho0 + structured_tdot(c.segment(1, K), y_new);
432 lastWasBlock =
false;
435 gammaPrev = gamma_save;
440 Ypp = Yp.leftCols(p);
441 Zpp = Zp.leftCols(p);
452 m_isInitialized =
true;
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
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.
constexpr Index size() const noexcept