Evaluating Matrix Functions by Resummations on Graphs: the Method of Path-Sums
We introduce the method of path-sums which is a tool for exactly evaluating a function of a discrete matrix with possibly non-commuting entries, based on the closed-form resummation of infinite families of terms in the corresponding Taylor series. If the matrix is finite, our approach yields the exa...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1797072957173923840 |
|---|---|
| author | Giscard, P Thwaite, S Jaksch, D |
| author_facet | Giscard, P Thwaite, S Jaksch, D |
| author_sort | Giscard, P |
| collection | OXFORD |
| description | We introduce the method of path-sums which is a tool for exactly evaluating a function of a discrete matrix with possibly non-commuting entries, based on the closed-form resummation of infinite families of terms in the corresponding Taylor series. If the matrix is finite, our approach yields the exact result in a finite number of steps. We achieve this by combining a mapping between matrix powers and walks on a weighted directed graph with a universal graph-theoretic result on the structure of such walks. We present path-sum expressions for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We show that the quasideterminants of a matrix can be naturally formulated in terms of a path-sum, and present examples of the application of the path-sum method. We show that obtaining the inversion height of a matrix inverse and of quasideterminants is an NP-complete problem. |
| first_indexed | 2024-03-06T23:15:09Z |
| format | Journal article |
| id | oxford-uuid:66e06a6c-0d18-4aca-82f4-9129d61c0183 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:15:09Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:66e06a6c-0d18-4aca-82f4-9129d61c01832022-03-26T18:34:39ZEvaluating Matrix Functions by Resummations on Graphs: the Method of Path-SumsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:66e06a6c-0d18-4aca-82f4-9129d61c0183EnglishSymplectic Elements at Oxford2011Giscard, PThwaite, SJaksch, DWe introduce the method of path-sums which is a tool for exactly evaluating a function of a discrete matrix with possibly non-commuting entries, based on the closed-form resummation of infinite families of terms in the corresponding Taylor series. If the matrix is finite, our approach yields the exact result in a finite number of steps. We achieve this by combining a mapping between matrix powers and walks on a weighted directed graph with a universal graph-theoretic result on the structure of such walks. We present path-sum expressions for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We show that the quasideterminants of a matrix can be naturally formulated in terms of a path-sum, and present examples of the application of the path-sum method. We show that obtaining the inversion height of a matrix inverse and of quasideterminants is an NP-complete problem. |
| spellingShingle | Giscard, P Thwaite, S Jaksch, D Evaluating Matrix Functions by Resummations on Graphs: the Method of Path-Sums |
| title | Evaluating Matrix Functions by Resummations on Graphs: the Method of
Path-Sums |
| title_full | Evaluating Matrix Functions by Resummations on Graphs: the Method of
Path-Sums |
| title_fullStr | Evaluating Matrix Functions by Resummations on Graphs: the Method of
Path-Sums |
| title_full_unstemmed | Evaluating Matrix Functions by Resummations on Graphs: the Method of
Path-Sums |
| title_short | Evaluating Matrix Functions by Resummations on Graphs: the Method of
Path-Sums |
| title_sort | evaluating matrix functions by resummations on graphs the method of path sums |
| work_keys_str_mv | AT giscardp evaluatingmatrixfunctionsbyresummationsongraphsthemethodofpathsums AT thwaites evaluatingmatrixfunctionsbyresummationsongraphsthemethodofpathsums AT jakschd evaluatingmatrixfunctionsbyresummationsongraphsthemethodofpathsums |