This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen

Bug 840

Summary: Sylvester-like solver
Product: Eigen Reporter: Chen-Pang He <jdh8>
Component: Unsupported modulesAssignee: Chen-Pang He <jdh8>
Status: ASSIGNED ---    
Severity: Feature Request CC: b7.10110111, chtz, gael.guennebaud
Priority: Normal    
Version: unspecified   
Hardware: All   
OS: All   
Whiteboard:
Bug Depends on: 934, 839    
Bug Blocks:    
Attachments:
Description Flags
Current incomplete work none

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.