This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 840 - Sylvester-like solver
Summary: Sylvester-like solver
Status: ASSIGNED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Unsupported modules (show other bugs)
Version: unspecified
Hardware: All All
: Normal Feature Request
Assignee: Chen-Pang He
URL:
Whiteboard:
Keywords:
Depends on: 934 839
Blocks:
  Show dependency treegraph
 
Reported: 2014-07-07 15:12 UTC by Chen-Pang He
Modified: 2019-12-04 13:30 UTC (History)
3 users (show)



Attachments
Current incomplete work (5.77 KB, application/x-xz)
2014-08-05 19:04 UTC, Chen-Pang He
no flags Details

Description Chen-Pang He 2014-07-07 15:12:27 UTC
This is an announcement for whom is interested in the same topic.

I'd like to write a module that provides solvers for Sylvester-like equations.

- Lyapunov equation (CT) AX + XA* = Q
- Lyapunov equation (DT) AXA* - X = Q
- Sylvester equation (CT) AX + XB = C (1)
- Sylvester equation (DT) AXB - X = C

More equations may be added after beta.

Algorithm
---------
A classical solution is Bartels–Stewart algorithm.  Take (1) for example.  We compute the Schur forms of A and B, viz. UTU* and VSV*, transforming the equation into (2).

UTU*X + XVSV* = C (2)

Apply U* on the left and V on the right to transform (2) into the equation below.

T(U*XV) + (U*XV)S = U*CV

Parentheses are added to aid reading.  A general SYCT (Sylvester CT) is reduced to triangular SYCT.

However, if A and B are to be used only once, a better way is *not* to compute the Schur form of the larger.  We stop at cheaper Hessenberg form.  Assume the larger is A without losing generality.  Set the Hessenberg form of A is UHU*.

H(U*XV) + (U*XV)S = U*CV

Now we see the trade-off: we have to solve Hessenberg instead of triangular system.

Challenges
----------
- Blocking (different depths on-the-left and on-the-right)
- Do we need HessenbergView or PartialPivLU is enough?
- RealSchur or ComplexSchur for real matrices?
  * Do we need QuasiTriangularView, or HessenbergView or even PartialPivLU is enough?
  * Blocking is more tricky
Comment 1 Chen-Pang He 2014-08-05 19:04:02 UTC
Created attachment 482 [details]
Current incomplete work

I'm slowing down for my (medical) studies, but I'm still keeping an eye on this.
Comment 2 Ruslan 2017-01-26 11:32:02 UTC
Hello, what is current status of this feature?
Comment 3 Chen-Pang He 2017-02-04 07:42:17 UTC
It is in the 'sylvester' branch in my clone of Eigen, but my lastest commit was in September 2016. :(

https://bitbucket.org/jdh8/eigen/branch/sylvester
Comment 4 Nobody 2019-12-04 13:30:21 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/840.

Note You need to log in before you can comment on or make changes to this bug.