Timeline for Accurately Computing a Positive Vector in the Nullspace of a Matrix
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2020 at 18:33 | comment | added | Federico Poloni | Great! I am glad to be of help, @cyfirx . | |
| Jun 27, 2020 at 16:49 | comment | added | cyfirx | Following your advice I have implemented something similar to the GTH algorithm to solve my problem nicely. Thank you very much! | |
| Jun 27, 2020 at 16:48 | vote | accept | cyfirx | ||
| Jun 23, 2020 at 5:58 | comment | added | Federico Poloni | Numerically, there are dedicated algorithms to compute this vector with very high precision; see e.g. ams.org/journals/mcom/2002-71-237/S0025-5718-01-01325-4/… . In your case, the algorithms in their Section 3 (GTH-like algorithm) should do the job, since essentially you just have to compute an accurate LU decomposition to find the nullspace. | |
| Jun 23, 2020 at 5:55 | comment | added | Federico Poloni | Irreducible M-matrices have a kernel of dimension 1, spanned by a vector with positive entries: this is a consequence of the Perron--Frobenius theorem, and should be treated in Berman--Plemmons (it's a while since I used that book though, so I don't have an exact reference). So you should have only one zero singular value, in exact arithmetic, and the other ones are spurious. That is the first interesting bit of information. | |
| Jun 22, 2020 at 22:53 | comment | added | cyfirx | Yes, you're right! If I interpret the matrix as a directed graph (ignoring the diagonal elements) there is a path between any two given nodes, thus the entire graph is strongly connected. But I don't see how this helps with the nullspace calculation. | |
| Jun 22, 2020 at 15:31 | comment | added | Federico Poloni | There is probably something inside the scipy graph libraries, but I am not sure exactly where to look. Also, it is possible that this comes from free from the structure of your problem. | |
| Jun 22, 2020 at 15:29 | comment | added | Federico Poloni | I am glad to hear that the M-matrix tip helped! No, that is a different kind of reduction: you reorder column and row indices symmetrically so that your matrix becomes block triangular with irreducible blocks. Essentially, you wish to split the directed graph associated with the matrix into strongly connected components. This is purely a symbolic operation, without actual floating-point computations in it. | |
| Jun 22, 2020 at 15:18 | comment | added | cyfirx | Numerical investigations thus far have supported the assumption that they are indeed M-matrices but I am not sure how to implement the block-triangularisation (I assume this means to split the matrix into blocks and perform row operations on the entire matrix until each block is zero above or below it's diagonal) and then extract the nullspace vector. Will I find a library function to do this eg scipy or will I need to write my own? | |
| Jun 22, 2020 at 15:07 | comment | added | cyfirx | Thanks for the summary. I have attempted a linear programming approach which improves the accuracy but fails for a significant number of cases and does not perform well. For this reason I have begun to investigate M-matrices as you have suggested and I think I may be able to prove my A is an M-matrix using the characterisation detailed in "R. Plemmons, Nonnegative Matrices in the Mathematical Science" p149, however I need time to check this and familiarise myself with some issues with the notation. | |
| Jun 22, 2020 at 7:07 | history | answered | Federico Poloni | CC BY-SA 4.0 |