Resolvent matrix












2












$begingroup$


Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?



Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of $A$. But what about $N(x)$?



I am aware of the Leverrier-Fadeev algorithm, which requires $O(n^4)$ operations if $A$ is $ntimes n$. Moreover, it makes use of power iteration, which can lead to numerical instability.










share|cite|improve this question









$endgroup$












  • $begingroup$
    What is the Leverrier-Fadeev algorithm you mentioned?
    $endgroup$
    – DisintegratingByParts
    Nov 27 '14 at 11:27










  • $begingroup$
    @Dis, this one.
    $endgroup$
    – J. M. is not a mathematician
    Aug 28 '17 at 4:32
















2












$begingroup$


Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?



Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of $A$. But what about $N(x)$?



I am aware of the Leverrier-Fadeev algorithm, which requires $O(n^4)$ operations if $A$ is $ntimes n$. Moreover, it makes use of power iteration, which can lead to numerical instability.










share|cite|improve this question









$endgroup$












  • $begingroup$
    What is the Leverrier-Fadeev algorithm you mentioned?
    $endgroup$
    – DisintegratingByParts
    Nov 27 '14 at 11:27










  • $begingroup$
    @Dis, this one.
    $endgroup$
    – J. M. is not a mathematician
    Aug 28 '17 at 4:32














2












2








2


1



$begingroup$


Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?



Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of $A$. But what about $N(x)$?



I am aware of the Leverrier-Fadeev algorithm, which requires $O(n^4)$ operations if $A$ is $ntimes n$. Moreover, it makes use of power iteration, which can lead to numerical instability.










share|cite|improve this question









$endgroup$




Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?



Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of $A$. But what about $N(x)$?



I am aware of the Leverrier-Fadeev algorithm, which requires $O(n^4)$ operations if $A$ is $ntimes n$. Moreover, it makes use of power iteration, which can lead to numerical instability.







linear-algebra dynamical-systems






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 26 '14 at 10:12









MicheleMichele

112




112












  • $begingroup$
    What is the Leverrier-Fadeev algorithm you mentioned?
    $endgroup$
    – DisintegratingByParts
    Nov 27 '14 at 11:27










  • $begingroup$
    @Dis, this one.
    $endgroup$
    – J. M. is not a mathematician
    Aug 28 '17 at 4:32


















  • $begingroup$
    What is the Leverrier-Fadeev algorithm you mentioned?
    $endgroup$
    – DisintegratingByParts
    Nov 27 '14 at 11:27










  • $begingroup$
    @Dis, this one.
    $endgroup$
    – J. M. is not a mathematician
    Aug 28 '17 at 4:32
















$begingroup$
What is the Leverrier-Fadeev algorithm you mentioned?
$endgroup$
– DisintegratingByParts
Nov 27 '14 at 11:27




$begingroup$
What is the Leverrier-Fadeev algorithm you mentioned?
$endgroup$
– DisintegratingByParts
Nov 27 '14 at 11:27












$begingroup$
@Dis, this one.
$endgroup$
– J. M. is not a mathematician
Aug 28 '17 at 4:32




$begingroup$
@Dis, this one.
$endgroup$
– J. M. is not a mathematician
Aug 28 '17 at 4:32










2 Answers
2






active

oldest

votes


















0












$begingroup$

Since $A$ is triangular, you may try to first diagonalize if, $A=PDP^{-1}$. You already know what the eigenvalues of $A$ are. Then, $$(xI-A)^{-1} = (P(xI-D)P^{-1})^{-1} = P(xI-D)^{-1}P^{-1}$$ and $(xI-D)^{-1}$ is trivial to calculate. Does this help?






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Not much unfortunately, because $A$ may not be diagonalizable.
    $endgroup$
    – Michele
    Nov 26 '14 at 12:15










  • $begingroup$
    @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
    $endgroup$
    – 5xum
    Nov 26 '14 at 12:21










  • $begingroup$
    Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
    $endgroup$
    – Michele
    Nov 26 '14 at 13:00





















0












$begingroup$

$(xI-A)^{-1}=Adj(xI-A)/p(x)$ where $p(x)$ is the (known) characteristic polynomial of $A$. On the other hand, $Adj(sI-A)=Delta p(s,A)$ where $Delta p(s,t)=dfrac{p(s)-p(t)}{s-t}$ (a symmetric polynomial).



For example, let $n=3,p(x)=x^3-2x^2-3x+2$; then



$Delta p(s,t)=dfrac{s^3-t^3-2s^2+2t^2-3s+3t}{s-t}=s^2+st+t^2-2s-2t-3$.



Finally $Adj(xI-A)=(x^2-2x-3)I+(x-2)A+A^2$.



EDIT. The resolvent is essentially used to calculate $f(A)$ when $f$ is an holomorphic function.



Here $(xI-A)^{-1}=sum_j a_j(x)/p(x) A^j$ where $a_j$ is a polynomial.



Then $f(A)=1/2ipisum_j (int_{gamma} f(x)a_j(x)/p(x)dx) A^j$ where $gamma$ is a ad hoc curve. Consequently, we must only calculate $n$ numerical integrals.



In particular, when $lambda_1,cdots,lambda_n$, the roots of $p$, are simple:



$f(A)=sum_j(sum_k f(lambda_k)a_j(lambda_k)/p'(lambda_k)) A^j$.



Anyway, the complexity of the calculation is that of the computation of the $(A^j)_j$, that is here $sim n^4/6$ (of course, if the calculation of the Jordan form of $A$ is stable, then we can do the job with complexity about $30 n³$).






share|cite|improve this answer











$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1039453%2fresolvent-matrix%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    Since $A$ is triangular, you may try to first diagonalize if, $A=PDP^{-1}$. You already know what the eigenvalues of $A$ are. Then, $$(xI-A)^{-1} = (P(xI-D)P^{-1})^{-1} = P(xI-D)^{-1}P^{-1}$$ and $(xI-D)^{-1}$ is trivial to calculate. Does this help?






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Not much unfortunately, because $A$ may not be diagonalizable.
      $endgroup$
      – Michele
      Nov 26 '14 at 12:15










    • $begingroup$
      @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
      $endgroup$
      – 5xum
      Nov 26 '14 at 12:21










    • $begingroup$
      Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
      $endgroup$
      – Michele
      Nov 26 '14 at 13:00


















    0












    $begingroup$

    Since $A$ is triangular, you may try to first diagonalize if, $A=PDP^{-1}$. You already know what the eigenvalues of $A$ are. Then, $$(xI-A)^{-1} = (P(xI-D)P^{-1})^{-1} = P(xI-D)^{-1}P^{-1}$$ and $(xI-D)^{-1}$ is trivial to calculate. Does this help?






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Not much unfortunately, because $A$ may not be diagonalizable.
      $endgroup$
      – Michele
      Nov 26 '14 at 12:15










    • $begingroup$
      @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
      $endgroup$
      – 5xum
      Nov 26 '14 at 12:21










    • $begingroup$
      Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
      $endgroup$
      – Michele
      Nov 26 '14 at 13:00
















    0












    0








    0





    $begingroup$

    Since $A$ is triangular, you may try to first diagonalize if, $A=PDP^{-1}$. You already know what the eigenvalues of $A$ are. Then, $$(xI-A)^{-1} = (P(xI-D)P^{-1})^{-1} = P(xI-D)^{-1}P^{-1}$$ and $(xI-D)^{-1}$ is trivial to calculate. Does this help?






    share|cite|improve this answer









    $endgroup$



    Since $A$ is triangular, you may try to first diagonalize if, $A=PDP^{-1}$. You already know what the eigenvalues of $A$ are. Then, $$(xI-A)^{-1} = (P(xI-D)P^{-1})^{-1} = P(xI-D)^{-1}P^{-1}$$ and $(xI-D)^{-1}$ is trivial to calculate. Does this help?







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Nov 26 '14 at 10:31









    5xum5xum

    91.4k394161




    91.4k394161












    • $begingroup$
      Not much unfortunately, because $A$ may not be diagonalizable.
      $endgroup$
      – Michele
      Nov 26 '14 at 12:15










    • $begingroup$
      @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
      $endgroup$
      – 5xum
      Nov 26 '14 at 12:21










    • $begingroup$
      Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
      $endgroup$
      – Michele
      Nov 26 '14 at 13:00




















    • $begingroup$
      Not much unfortunately, because $A$ may not be diagonalizable.
      $endgroup$
      – Michele
      Nov 26 '14 at 12:15










    • $begingroup$
      @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
      $endgroup$
      – 5xum
      Nov 26 '14 at 12:21










    • $begingroup$
      Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
      $endgroup$
      – Michele
      Nov 26 '14 at 13:00


















    $begingroup$
    Not much unfortunately, because $A$ may not be diagonalizable.
    $endgroup$
    – Michele
    Nov 26 '14 at 12:15




    $begingroup$
    Not much unfortunately, because $A$ may not be diagonalizable.
    $endgroup$
    – Michele
    Nov 26 '14 at 12:15












    $begingroup$
    @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
    $endgroup$
    – 5xum
    Nov 26 '14 at 12:21




    $begingroup$
    @Michele Then you can at least find the Jordan normal form of the matrix. In any case, even simply calculating $(xI-A)^{-1}$ is not a difficult operation to perform if $A$ is triangular.
    $endgroup$
    – 5xum
    Nov 26 '14 at 12:21












    $begingroup$
    Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
    $endgroup$
    – Michele
    Nov 26 '14 at 13:00






    $begingroup$
    Thanks. What is the computational cost of computing the Jordan Normal Form for a triangular $A$? In any case, note that the difficulty here is that we have to carry out a symbolic computation, because of the indeterminate $x$ (I know of course that for specific values of $x$ this is easy).
    $endgroup$
    – Michele
    Nov 26 '14 at 13:00













    0












    $begingroup$

    $(xI-A)^{-1}=Adj(xI-A)/p(x)$ where $p(x)$ is the (known) characteristic polynomial of $A$. On the other hand, $Adj(sI-A)=Delta p(s,A)$ where $Delta p(s,t)=dfrac{p(s)-p(t)}{s-t}$ (a symmetric polynomial).



    For example, let $n=3,p(x)=x^3-2x^2-3x+2$; then



    $Delta p(s,t)=dfrac{s^3-t^3-2s^2+2t^2-3s+3t}{s-t}=s^2+st+t^2-2s-2t-3$.



    Finally $Adj(xI-A)=(x^2-2x-3)I+(x-2)A+A^2$.



    EDIT. The resolvent is essentially used to calculate $f(A)$ when $f$ is an holomorphic function.



    Here $(xI-A)^{-1}=sum_j a_j(x)/p(x) A^j$ where $a_j$ is a polynomial.



    Then $f(A)=1/2ipisum_j (int_{gamma} f(x)a_j(x)/p(x)dx) A^j$ where $gamma$ is a ad hoc curve. Consequently, we must only calculate $n$ numerical integrals.



    In particular, when $lambda_1,cdots,lambda_n$, the roots of $p$, are simple:



    $f(A)=sum_j(sum_k f(lambda_k)a_j(lambda_k)/p'(lambda_k)) A^j$.



    Anyway, the complexity of the calculation is that of the computation of the $(A^j)_j$, that is here $sim n^4/6$ (of course, if the calculation of the Jordan form of $A$ is stable, then we can do the job with complexity about $30 n³$).






    share|cite|improve this answer











    $endgroup$


















      0












      $begingroup$

      $(xI-A)^{-1}=Adj(xI-A)/p(x)$ where $p(x)$ is the (known) characteristic polynomial of $A$. On the other hand, $Adj(sI-A)=Delta p(s,A)$ where $Delta p(s,t)=dfrac{p(s)-p(t)}{s-t}$ (a symmetric polynomial).



      For example, let $n=3,p(x)=x^3-2x^2-3x+2$; then



      $Delta p(s,t)=dfrac{s^3-t^3-2s^2+2t^2-3s+3t}{s-t}=s^2+st+t^2-2s-2t-3$.



      Finally $Adj(xI-A)=(x^2-2x-3)I+(x-2)A+A^2$.



      EDIT. The resolvent is essentially used to calculate $f(A)$ when $f$ is an holomorphic function.



      Here $(xI-A)^{-1}=sum_j a_j(x)/p(x) A^j$ where $a_j$ is a polynomial.



      Then $f(A)=1/2ipisum_j (int_{gamma} f(x)a_j(x)/p(x)dx) A^j$ where $gamma$ is a ad hoc curve. Consequently, we must only calculate $n$ numerical integrals.



      In particular, when $lambda_1,cdots,lambda_n$, the roots of $p$, are simple:



      $f(A)=sum_j(sum_k f(lambda_k)a_j(lambda_k)/p'(lambda_k)) A^j$.



      Anyway, the complexity of the calculation is that of the computation of the $(A^j)_j$, that is here $sim n^4/6$ (of course, if the calculation of the Jordan form of $A$ is stable, then we can do the job with complexity about $30 n³$).






      share|cite|improve this answer











      $endgroup$
















        0












        0








        0





        $begingroup$

        $(xI-A)^{-1}=Adj(xI-A)/p(x)$ where $p(x)$ is the (known) characteristic polynomial of $A$. On the other hand, $Adj(sI-A)=Delta p(s,A)$ where $Delta p(s,t)=dfrac{p(s)-p(t)}{s-t}$ (a symmetric polynomial).



        For example, let $n=3,p(x)=x^3-2x^2-3x+2$; then



        $Delta p(s,t)=dfrac{s^3-t^3-2s^2+2t^2-3s+3t}{s-t}=s^2+st+t^2-2s-2t-3$.



        Finally $Adj(xI-A)=(x^2-2x-3)I+(x-2)A+A^2$.



        EDIT. The resolvent is essentially used to calculate $f(A)$ when $f$ is an holomorphic function.



        Here $(xI-A)^{-1}=sum_j a_j(x)/p(x) A^j$ where $a_j$ is a polynomial.



        Then $f(A)=1/2ipisum_j (int_{gamma} f(x)a_j(x)/p(x)dx) A^j$ where $gamma$ is a ad hoc curve. Consequently, we must only calculate $n$ numerical integrals.



        In particular, when $lambda_1,cdots,lambda_n$, the roots of $p$, are simple:



        $f(A)=sum_j(sum_k f(lambda_k)a_j(lambda_k)/p'(lambda_k)) A^j$.



        Anyway, the complexity of the calculation is that of the computation of the $(A^j)_j$, that is here $sim n^4/6$ (of course, if the calculation of the Jordan form of $A$ is stable, then we can do the job with complexity about $30 n³$).






        share|cite|improve this answer











        $endgroup$



        $(xI-A)^{-1}=Adj(xI-A)/p(x)$ where $p(x)$ is the (known) characteristic polynomial of $A$. On the other hand, $Adj(sI-A)=Delta p(s,A)$ where $Delta p(s,t)=dfrac{p(s)-p(t)}{s-t}$ (a symmetric polynomial).



        For example, let $n=3,p(x)=x^3-2x^2-3x+2$; then



        $Delta p(s,t)=dfrac{s^3-t^3-2s^2+2t^2-3s+3t}{s-t}=s^2+st+t^2-2s-2t-3$.



        Finally $Adj(xI-A)=(x^2-2x-3)I+(x-2)A+A^2$.



        EDIT. The resolvent is essentially used to calculate $f(A)$ when $f$ is an holomorphic function.



        Here $(xI-A)^{-1}=sum_j a_j(x)/p(x) A^j$ where $a_j$ is a polynomial.



        Then $f(A)=1/2ipisum_j (int_{gamma} f(x)a_j(x)/p(x)dx) A^j$ where $gamma$ is a ad hoc curve. Consequently, we must only calculate $n$ numerical integrals.



        In particular, when $lambda_1,cdots,lambda_n$, the roots of $p$, are simple:



        $f(A)=sum_j(sum_k f(lambda_k)a_j(lambda_k)/p'(lambda_k)) A^j$.



        Anyway, the complexity of the calculation is that of the computation of the $(A^j)_j$, that is here $sim n^4/6$ (of course, if the calculation of the Jordan form of $A$ is stable, then we can do the job with complexity about $30 n³$).







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Sep 4 '17 at 10:24

























        answered Sep 2 '17 at 15:54









        loup blancloup blanc

        23.7k21851




        23.7k21851






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1039453%2fresolvent-matrix%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Plaza Victoria

            Puebla de Zaragoza

            Musa