Le 13/07/2015 10:36, michele.bora...@imtlucca.it a écrit :
Hi all! My name is Michele Borassi, and I recently entered this great community for a Google Summer of Code project. Among other works, I am including in Sage an algorithm for computing the Cuthill-McKee and the King orderings [1,2], which are heuristics used to approximate the bandwidth of a graph [3] (ticket 18876, [4]). Since the bandwidth of a graph is the bandwidth of its adjacency matrix, maybe these algorithms might be useful also in the matrix context. However, before including them, since I work with graphs and I know very little about matrix algorithms, I have some doubts:* Are these algorithm really interesting for matrix analysis? * In case, where and how should I include these algorithms? * If it is more complicated than this), could you provide more information? For instance, if you need related routines, like permuting rows and columns according to these orderings, or maybe you would like to integrate this work with other algorithms. In case, I might open a new ticket that takes care of all these things.
Hi,These methods have been widely used for the solution of large linear systems one encounter in the discretization of Partial Differential Equations; these systems are sparse (O(n) non zeros for an order n); the factorizations (LU, Cholesky) create new non zeros terms inside the band. So reducing the band width is a necessity. Nowadays, direct methods for sparse systems (SuperLU, Mumps) are based on more sophisticated ideas (like nested dissection).
The Cuthill-Mac Kee algorithm (actually the reverse Cuthill-Mac Kee version) is implemented in scipy (scipy.sparse.csgraph improvements).
I think this is the right place for this. Yours t.d.
For any other comment, doubt, or suggestion, please feel free to contact me! Thank you very much for your help! Best, Michele [1] https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm [2] http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/king_ordering.html [3] https://en.wikipedia.org/wiki/Graph_bandwidth [4] http://trac.sagemath.org/ticket/18876 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com <mailto:sage-devel+unsubscr...@googlegroups.com>. To post to this group, send email to sage-devel@googlegroups.com <mailto:sage-devel@googlegroups.com>. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
-- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
<<attachment: tdumont.vcf>>
