Skip to content
GitLab
    • GitLab: the DevOps platform
    • Explore GitLab
    • Install GitLab
    • How GitLab compares
    • Get started
    • GitLab docs
    • GitLab Learn
  • Pricing
  • Talk to an expert
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
    • Switch to GitLab Next
    Projects Groups Topics Snippets
  • Register
  • Sign in
  • eigen eigen
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
    • Locked files
  • Issues 684
    • Issues 684
    • List
    • Boards
    • Service Desk
    • Milestones
    • Requirements
  • Custom issue tracker
    • Custom issue tracker
  • Merge requests 21
    • Merge requests 21
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test cases
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Packages and registries
    • Packages and registries
    • Package Registry
    • Container Registry
    • Infrastructure Registry
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • libeigenlibeigen
  • eigeneigen
  • Issues
  • #840
Closed
Open
Issue created Dec 04, 2019 by Eigen Bugzilla@eigenbzReporter

Sylvester-like solver

Submitted by Chen-Pang He

Assigned to Chen-Pang He

Link to original bugzilla bug (#840)

Description

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).

UTUX + XVSV = C (2)

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

T(UXV) + (UXV)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(UXV) + (UXV)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

Depends on

#934 #839 (closed)

Edited Dec 05, 2019 by Eigen Bugzilla
Assignee
Assign to
Time tracking