Skip to main content
MathOverflow

Return to Question

added 2 characters in body; added 6 characters in body; added 7 characters in body; added 43 characters in body; deleted 5 characters in body; added 64 characters in body
Source Link
Nancy
Nancy
  • 41
  • 2

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, 

where $E$ is an $n \times n$ identity matrix, $0 < a < 1$$ a \in (0,1)$ is a scalar, and $X$ is a sparse stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then,

do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? (to reduce its $O(n^3)$ complexity is preferable, or approximate solution is also acceptable) ? Thanks in advance!

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, where $E$ is an $n \times n$ identity matrix, $0 < a < 1$ is a scalar, and $X$ is a stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? Thanks in advance!

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, 

where $E$ is an $n \times n$ identity matrix, $ a \in (0,1)$ is a scalar, and $X$ is a sparse stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1),

do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? (to reduce its $O(n^3)$ complexity is preferable, or approximate solution is also acceptable) ? Thanks in advance!

added 4 characters in body
Source Link
S. Carnahan ♦
S. Carnahan ♦
  • 45.7k
  • 6
  • 114
  • 220

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, where $E$ is an $n \times n$ identity matrix, $0<a<1$$0 < a < 1$ is a scalar, and $X$ is a stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? Thanks in advance!

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, where $E$ is an $n \times n$ identity matrix, $0<a<1$ is a scalar, and $X$ is a stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? Thanks in advance!

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, where $E$ is an $n \times n$ identity matrix, $0 < a < 1$ is a scalar, and $X$ is a stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? Thanks in advance!

Source Link
Nancy
Nancy
  • 41
  • 2

efficient way to compute the inversion of the following matrix

Hi, there

I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special matrix ${(E-a \cdot X)}^{-1}$, where $E$ is an $n \times n$ identity matrix, $0<a<1$ is a scalar, and $X$ is a stochastic matrix (the sum of each row is 1, and all its entries are between 0 and 1). Then do you have some ideas to compute ${(E-a \cdot X)}^{-1}$ as fast as you can? Thanks in advance!