In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Cuthill-McKee-Algorithmus (de)
- Algoritmo de Cuthill-McKee (es)
- Cuthill–McKee algorithm (en)
- Algoritmo Cuthill-McKee (it)
- カットヒル・マキー法 (ja)
- Алгоритм Катхилла — Макки (ru)
- Алгоритм Катхілл — Маккі (uk)
|
| rdfs:comment
| - En el subcampo matemático de la teoría de matrices, el algoritmo de Cuthill-McKee es un algoritmo para reducir el ancho de banda de una matriz simétrica dispersa. El algoritmo invertido de Cuthill-McKee (RCM, por las siglas inglesas Reverse Cuthill-McKee) es el mismo algoritmo pero con los índices resultantes invertidos. En el ámbito práctico, emplear este último es generalmente una mejor solución. (es)
- 行列を扱う数学分野において、カットヒル・マキー法 (カットヒル・マッキー並べ替えとも、Cuthill–McKee algorithm, CM) は Elizabeth Cuthill と J. McKee に因んで名付けられた、対称なパターンを持つ疎行列をの小さいの形に並べ替えるアルゴリズムである。同じアルゴリズムだが、指数が逆順となる、逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm, RCM) と呼ばれる Alan George によるアルゴリズムもある。実用上、ガウシアン除去と共に適用した場合は CM 並べ替えよりもフィルインが少くなることが知られている。 カットヒル・マキー法 はグラフ理論上で標準的に用いられる、幅優先探索アルゴリズムの一変種である。Ri (i=1,2,..) を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 Ri+1 は集合 Ri 内の全ノードの隣接頂点から生成される。 これらのノードは次数が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。 (ja)
- L'algoritmo Cuthill-McKee (CM), ideato da Elizabeth Cuthill e J. McKee, permette di permutare una matrice sparsa simmetrica in una matrice a banda più compatta e quindi più facilmente risolvibile. L'algoritmo Cuthill-McKee inverso (RCM), proposto da Alan George, adotta lo stesso procedimento ma sistemando i termini della matrice con i pedici invertiti: in generale ciò consente, rispetto al CM, di mantenere un maggior numero di termini nulli quando l'algoritmo di Gauss viene successivamente impiegato. (it)
- Алгоритм Ка́тхилла — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения разреженных симметричных матриц. Назван по именам разработчиков — Элизабет Катхилл и Джеймса Макки. Обратный алгоритм Катхилла — Макки (RCM, reverse Cuthill—McKee) — тот же самый алгоритм с обратной нумераций индексов. (ru)
- In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied. (en)
- Der Cuthill-McKee-Algorithmus (benannt nach Elizabeth Cuthill und James McKee) ist in der numerischen Mathematik ein Algorithmus, der eine symmetrische dünnbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite transformiert. Für Bandmatrizen existieren sehr effiziente Berechnungsalgorithmen, beispielsweise für die Lösung von sehr großen linearen Gleichungssystemen (siehe BLAS). Der Cuthill-McKee-Algorithmus unterscheidet sich von der Breitensuche für Graphen durch seine Reihenfolge, die durch Nummerierung adjazenter Knoten anhand ihres Grades ermittelt wird. (de)
- Алгоритм Катхілл — Маккі (КМ), названий на честь Елізабет Катхілл і Джеймса Маккі, це алгоритм переведення розрідженої матриці, яка симетрично розріджена, у смугову матрицю з малою шириною смуги, шляхом переставляння рядків і стовпчиків. Зворотний алгоритм Катхілл Маккі (ЗКМ) запропонований Аланом Джорджем — це той самий алгоритм, але з оберненим порядком індексування вершин. На практиці це допомагає отримати менше заповнювання нульових позицій порівняння з КМ впорядкуванням при використанні методу Гауса. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| thumbnail
| |
| has abstract
| - Der Cuthill-McKee-Algorithmus (benannt nach Elizabeth Cuthill und James McKee) ist in der numerischen Mathematik ein Algorithmus, der eine symmetrische dünnbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite transformiert. Für Bandmatrizen existieren sehr effiziente Berechnungsalgorithmen, beispielsweise für die Lösung von sehr großen linearen Gleichungssystemen (siehe BLAS). Der umgekehrte Cuthill-McKee-Algorithmus von Alan George ist derselbe Algorithmus mit umgekehrter Indexreihenfolge. Im Allgemeinen führt der umgekehrte Algorithmus zu einem geringeren Fill-in, wenn eine Gaußelimination durchgeführt wird. Unter „Fill-in“ versteht man das Entstehen von Nichtnull-Elementen an Positionen, die in der ursprünglichen Matrix mit Null besetzt sind. Der Cuthill-McKee-Algorithmus unterscheidet sich von der Breitensuche für Graphen durch seine Reihenfolge, die durch Nummerierung adjazenter Knoten anhand ihres Grades ermittelt wird. (de)
- In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied. The Cuthill McKee algorithm is a variant of the standard breadth-first searchalgorithm used in graph algorithms. It starts with a peripheral node and thengenerates levels for until all nodesare exhausted. The set is created from set by listing all vertices adjacent to all nodes in . These nodes are ordered according to predecessors and degree. (en)
- En el subcampo matemático de la teoría de matrices, el algoritmo de Cuthill-McKee es un algoritmo para reducir el ancho de banda de una matriz simétrica dispersa. El algoritmo invertido de Cuthill-McKee (RCM, por las siglas inglesas Reverse Cuthill-McKee) es el mismo algoritmo pero con los índices resultantes invertidos. En el ámbito práctico, emplear este último es generalmente una mejor solución. (es)
- 行列を扱う数学分野において、カットヒル・マキー法 (カットヒル・マッキー並べ替えとも、Cuthill–McKee algorithm, CM) は Elizabeth Cuthill と J. McKee に因んで名付けられた、対称なパターンを持つ疎行列をの小さいの形に並べ替えるアルゴリズムである。同じアルゴリズムだが、指数が逆順となる、逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm, RCM) と呼ばれる Alan George によるアルゴリズムもある。実用上、ガウシアン除去と共に適用した場合は CM 並べ替えよりもフィルインが少くなることが知られている。 カットヒル・マキー法 はグラフ理論上で標準的に用いられる、幅優先探索アルゴリズムの一変種である。Ri (i=1,2,..) を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 Ri+1 は集合 Ri 内の全ノードの隣接頂点から生成される。 これらのノードは次数が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。 (ja)
- L'algoritmo Cuthill-McKee (CM), ideato da Elizabeth Cuthill e J. McKee, permette di permutare una matrice sparsa simmetrica in una matrice a banda più compatta e quindi più facilmente risolvibile. L'algoritmo Cuthill-McKee inverso (RCM), proposto da Alan George, adotta lo stesso procedimento ma sistemando i termini della matrice con i pedici invertiti: in generale ciò consente, rispetto al CM, di mantenere un maggior numero di termini nulli quando l'algoritmo di Gauss viene successivamente impiegato. (it)
- Алгоритм Ка́тхилла — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения разреженных симметричных матриц. Назван по именам разработчиков — Элизабет Катхилл и Джеймса Макки. Обратный алгоритм Катхилла — Макки (RCM, reverse Cuthill—McKee) — тот же самый алгоритм с обратной нумераций индексов. (ru)
- Алгоритм Катхілл — Маккі (КМ), названий на честь Елізабет Катхілл і Джеймса Маккі, це алгоритм переведення розрідженої матриці, яка симетрично розріджена, у смугову матрицю з малою шириною смуги, шляхом переставляння рядків і стовпчиків. Зворотний алгоритм Катхілл Маккі (ЗКМ) запропонований Аланом Джорджем — це той самий алгоритм, але з оберненим порядком індексування вершин. На практиці це допомагає отримати менше заповнювання нульових позицій порівняння з КМ впорядкуванням при використанні методу Гауса. Алгоритм Катхілл — Маккі — це варіант стандартного пошуку в ширину, що використовується для графів. Він стартує з периферійної вершини і генерує для допоки не вичерпано всі вершини. Множина утворюється за допомогою множини збираючи всі вершини суміжні вершинам в . Ці вершини записуються в порядку збільшення степеня вершини. Цей останній момент і є відмінність від алгоритму пошуку в ширину. (uk)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
