4 ms·
I believe state of the art methods aim for linear time complexity, using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather t
by stabbles 9y ago
I believe state of the art methods aim for linear time complexity, using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2), and applying that in an iterative solver such as GMRES, which typically requires a constant number of iterations, because the matrix is just a slight perturbation of the identity matrix.
- Someone 9y ago"using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2)" If that's generic, couldn't we do matrix-matrix multiplication in O(n^2)? So, what are the limitations on that?
- pkhuong 9y agoThe results are approximate (but that's always true), and, IIUC, the quality of the approximation depends on how well the matrix can be factored into a local component (with values inversely proportional to |(i - j)|) and a sparse global component. Like petters writes above, "matrices of the form s^2 I + B, where B(i, j) depends on the distance between points i, j." The GMRES + FMM approach is more general, but FMM is less and less Fast as we move away from the structure above towards general matrices. This structure makes sense because it reflects physical reality… useful in when solving physics problems (: Less so when the matrix corresponds to logical/business constraints over 0/1 variables which may not be so local anymore.