1
$\begingroup$

Assume nonsymmetric, tridiagonal matrices $A, B \in \mathbb{R}^{n\times n}$ (where $n$ is in the order of 1000) and $A, B, AB$ are diagonalizable and have positive eigenvalues.

How do you efficiently compute the matrix-vector product of $$\vec{y}:=\sqrt{A B} \; \vec{x}$$ for a given $\vec{x}\in \mathbb{R}^n$ ?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Positive eigenvalues of $A,$ $B$ do not imply positive eigenvalues of $AB$. What is the $\sqrt{AB}$? $\endgroup$
    – Alexandre Eremenko
    Commented Dec 2, 2019 at 19:12
  • $\begingroup$ @AlexandreEremenko I edited my question: now A, B, and AB should have positive eigenvalues. Thus, $\sqrt{AB}$ should be uniquely defined. $\endgroup$
    – jack
    Commented Dec 3, 2019 at 8:02
  • 1
    $\begingroup$ How can a matrix always have a square root? Do you also have that the eigenvalues are distinct? Or, is the matrix diagonalizable? $\endgroup$
    – vidyarthi
    Commented Dec 3, 2019 at 10:12
  • $\begingroup$ @vidyarthi Lets assume that the matrix product is diagonalizable. $\endgroup$
    – jack
    Commented Dec 4, 2019 at 16:14
  • $\begingroup$ I'm not sure if this will work for you but it's what I'd try: 1. find some way to a priori bound the spectrum of $AB$, and consider a contour $\Gamma$ surrounding the spectrum once counterclockwise and completely contained in the right half-plane 2. Writing $R(z) = (z - AB)^{-1}$ for the resolvent, compute the contour integral of $\frac{1}{2 \pi i} \oint_\Gamma \sqrt{z} R(z) x dz$ 3. Approximate this integral by quadrature 4. At each quadrature point z_i, you've got to solve (z_i - AB)y = x, which is at least banded. $\endgroup$
    – pupshaw
    Commented Dec 4, 2019 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

One can use Krylov subspace based methods, i.e. rational Krylov methods work well. There is a paper and matlab code that works out of the box: http://guettel.com/markovfunmv/.

The approach is a black-box method that works for arbitrary functions and matrices. Thus, one might be able to optimize by the given info of positive eigenvalues and square root function.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .