Minimum degree algorithm - Revision history

Swinub: Typo

2024-07-15T18:09:56Z

Typo

← Previous revision		Revision as of 18:09, 15 July 2024
Line 1:		Line 1:
	{{short description\|Matrix manipulation ~~algorthim~~}}		{{short description\|Matrix manipulation algorithm}}
	In [[numerical analysis]], the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.		In [[numerical analysis]], the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.
	This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner—for example, in the preconditioned conjugate gradient algorithm.)		This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner—for example, in the preconditioned conjugate gradient algorithm.)

OAbot: Open access bot: arxiv added to citation with #oabot.

2023-08-13T04:19:10Z

Open access bot: arxiv added to citation with #oabot.

← Previous revision		Revision as of 04:19, 13 August 2023
Line 16:		Line 16:

	==References==		==References==
	*{{cite journal \|first1=Robert \|last1=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724–734 \|doi= 10.1137/1.9781611976465.45 \|isbn=978-1-61197-646-5 \|s2cid=198968052 }}		*{{cite journal \|first1=Robert \|last1=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724–734 \|doi= 10.1137/1.9781611976465.45 \|isbn=978-1-61197-646-5 \|s2cid=198968052 \|arxiv=1907.12119 }}
	*{{cite journal \|first1=Alan \|last1=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001\|osti=5686483 }}		*{{cite journal \|first1=Alan \|last1=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001\|osti=5686483 }}
	*{{citation\|first1=P.\|last1=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}		*{{citation\|first1=P.\|last1=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}

Citation bot: Alter: pages. Add: osti, s2cid, isbn, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 721/1134

2023-01-24T04:31:12Z

Alter: pages. Add: osti, s2cid, isbn, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 721/1134

← Previous revision		Revision as of 04:31, 24 January 2023
Line 16:		Line 16:

	==References==		==References==
	*{{cite journal \|~~first~~=Robert \|~~last~~=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=~~724-734~~ \|doi= 10.1137/1.9781611976465.45 }}		*{{cite journal \|first1=Robert \|last1=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724–734 \|doi= 10.1137/1.9781611976465.45 \|isbn=978-1-61197-646-5 \|s2cid=198968052 }}
	*{{cite journal \|~~first~~=Alan \|~~last~~=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}		*{{cite journal \|first1=Alan \|last1=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001\|osti=5686483 }}
	*{{citation\|~~first~~=P.\|~~last~~=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}		*{{citation\|first1=P.\|last1=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}
	*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}		*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}
	*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}		*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
	*{{cite journal \|~~first~~=W. F. \|~~last~~=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first1=W. F. \|last1=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

Matthewfahrbach: Add sentence about tight results of Cummings et al. (SODA 2021) for exact minimum degree orderings. Format and alphabetize references.

2022-08-07T00:37:21Z

Add sentence about tight results of Cummings et al. (SODA 2021) for exact minimum degree orderings. Format and alphabetize references.

← Previous revision		Revision as of 00:37, 7 August 2022
Line 13:		Line 13:
	of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with ''n'' vertices, with vertices ''i'' and ''j'' connected by an edge when <math>a_{ij} \ne 0</math>, and the ''degree'' is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.		of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with ''n'' vertices, with vertices ''i'' and ''j'' connected by an edge when <math>a_{ij} \ne 0</math>, and the ''degree'' is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.

	A version of the minimum degree algorithm was implemented in the [[MATLAB]] function '''symmmd''' (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function '''symamd''', which is faster. This is confirmed by theoretical analysis, which shows that for graphs on ''n'' vertices and ''m'' edges, MMD has a tight [[Big O notation\|upper bound]] of <math>O(n^2m)</math> on its ~~run~~ time, whereas for AMD a tight bound of <math>O(nm)</math> holds.		A version of the minimum degree algorithm was implemented in the [[MATLAB]] function '''symmmd''' (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function '''symamd''', which is faster. This is confirmed by theoretical analysis, which shows that for graphs with ''n'' vertices and ''m'' edges, MMD has a tight [[Big O notation\|upper bound]] of <math>O(n^2m)</math> on its running time, whereas for AMD a tight bound of <math>O(nm)</math> holds. Cummings, Fahrbach, and Fatehpuria designed an exact minimum degree algorithm with <math>O(nm)</math> running time, and showed that no such algorithm can exist that runs in time <math>O(nm^{1-\varepsilon})</math>, for any <math>\varepsilon > 0</math>, assuming the [[strong exponential time hypothesis]].

	==References==		==References==
			*{{cite journal \|first=Robert \|last=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724-734 \|doi= 10.1137/1.9781611976465.45 }}
			*{{cite journal \|first=Alan \|last=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}
		⚫	*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}
	*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}		*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}
	*{{cite ~~journal~~ \|first=~~Alan~~ \|last=~~George~~ \|~~first2~~=~~Joseph~~ ~~\|last2=Liu~~ ~~\|title=The evolution~~ of the ~~Minimum~~ ~~Degree~~ ~~Ordering~~ ~~Algorithm~~ ~~\|journal=[[SIAM~~ ~~Review]]~~ ~~\|volume=31~~ \|~~issue~~=1 \|~~pages~~=~~1–19~~ \|year=~~1989~~ \|~~jstor~~=~~2030845~~ \|~~doi~~=~~10.1137/1031001~~}}		*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
	*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}
	*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|editor-first=R. C. \|editor-last=Read \|location=New York \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
⚫	*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=~~December~~ 2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

GreenC bot: Rescued 1 archive link. Wayback Medic 2.5

2022-06-01T16:36:48Z

Rescued 1 archive link. Wayback Medic 2.5

← Previous revision		Revision as of 16:36, 1 June 2022
Line 16:		Line 16:

	==References==		==References==
	*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 }}		*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}
	*{{cite journal \|first=Alan \|last=George \|first2=Joseph \|last2=Liu \|title=The evolution of the Minimum Degree Ordering Algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}		*{{cite journal \|first=Alan \|last=George \|first2=Joseph \|last2=Liu \|title=The evolution of the Minimum Degree Ordering Algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}
	*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}

AndyFielding at 11:49, 12 May 2022

2022-05-12T11:49:50Z

← Previous revision		Revision as of 11:49, 12 May 2022
Line 1:		Line 1:
	{{short description\|Matrix manipulation algorthim}}		{{short description\|Matrix manipulation algorthim}}
	In [[numerical analysis]] the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.		In [[numerical analysis]], the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.
	This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a ~~preconditioner, for~~ example in the preconditioned conjugate gradient algorithm.)		This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner—for example, in the preconditioned conjugate gradient algorithm.)

	Minimum degree algorithms are often used in the [[finite element method]] where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.		Minimum degree algorithms are often used in the [[finite element method]] where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than on the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.

	Given a linear system		Given a linear system

85.137.109.22 at 19:54, 31 May 2021

2021-05-31T19:54:55Z

← Previous revision		Revision as of 19:54, 31 May 2021
Line 7:		Line 7:
	Given a linear system		Given a linear system
	:<math> \mathbf{A}\mathbf{x} = \mathbf{b}</math>		:<math> \mathbf{A}\mathbf{x} = \mathbf{b}</math>
	where '''A''' is an <math>n \times n</math> real symmetric sparse square matrix ~~the~~ Cholesky factor '''L''' will typically suffer 'fill in', that is have more non-zeros than the upper triangle of '''A'''. We seek a [[permutation matrix]] '''P''', so that the matrix		where '''A''' is an <math>n \times n</math> real symmetric sparse square matrix. The Cholesky factor '''L''' will typically suffer 'fill in', that is have more non-zeros than the upper triangle of '''A'''. We seek a [[permutation matrix]] '''P''', so that the matrix
	<math>\mathbf{P}^T\mathbf{A}\mathbf{P}</math>, which is also symmetric, has the least possible fill in its Cholesky factor. We solve the reordered system		<math>\mathbf{P}^T\mathbf{A}\mathbf{P}</math>, which is also symmetric, has the least possible fill in its Cholesky factor. We solve the reordered system
	:<math> \left(\mathbf{P}^T\mathbf{A}\mathbf{P}\right) \left(\mathbf{P}^T\mathbf{x}\right) = \mathbf{P}^T\mathbf{b}.</math>		:<math> \left(\mathbf{P}^T\mathbf{A}\mathbf{P}\right) \left(\mathbf{P}^T\mathbf{x}\right) = \mathbf{P}^T\mathbf{b}.</math>

The Anome: Adding short description: "Matrix manipulation algorthim" (Shortdesc helper)

2020-08-21T10:58:28Z

Adding short description: "Matrix manipulation algorthim" (Shortdesc helper)

← Previous revision		Revision as of 10:58, 21 August 2020
Line 1:		Line 1:
			{{short description\|Matrix manipulation algorthim}}
	In [[numerical analysis]] the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.		In [[numerical analysis]] the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.
	This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner, for example in the preconditioned conjugate gradient algorithm.)		This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner, for example in the preconditioned conjugate gradient algorithm.)

66.104.254.34: /* References */

2019-05-01T22:30:35Z

References

← Previous revision		Revision as of 22:30, 1 May 2019
Line 19:		Line 19:
	*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}
	*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|editor-first=R. C. \|editor-last=Read \|location=New York \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}		*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|editor-first=R. C. \|editor-last=Read \|location=New York \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
	*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=December 2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=~~http~~://~~oai~~.~~dtic~~.~~mil~~/~~oai~~/~~oai?verb=getRecord&metadataPrefix=html&identifier=ADA398632~~ \|publisher=Institute for Computer Applications in Science and Engineering}}		*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=December 2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

Cleopatran Apocalypse: Moving this into parenthetical .

2019-04-23T21:11:44Z

Moving this into parenthetical .

← Previous revision		Revision as of 21:11, 23 April 2019
Line 1:		Line 1:
	In [[numerical analysis]] the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.		In [[numerical analysis]] the '''minimum degree algorithm''' is an [[algorithm]] used to permute the rows and columns of a [[symmetric matrix\|symmetric]] [[sparse matrix]] before applying the [[Cholesky decomposition]], to reduce the number of non-zeros in the Cholesky factor.
	This results in reduced storage requirements and means that the Cholesky factor, or ~~sometimes~~ an incomplete Cholesky factor used as a preconditioner (for example in the preconditioned [[conjugate gradient]] algorithm~~) can be applied with fewer arithmetic operations~~.		This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner, for example in the preconditioned conjugate gradient algorithm.)

	Minimum degree algorithms are often used in the [[finite element method]] where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.		Minimum degree algorithms are often used in the [[finite element method]] where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.

← Previous revision		Revision as of 04:31, 24 January 2023
Line 16:		Line 16:

	==References==		==References==
	*{{cite journal \|~~first~~=Robert \|~~last~~=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=~~724-734~~ \|doi= 10.1137/1.9781611976465.45 }}		*{{cite journal \|first1=Robert \|last1=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724–734 \|doi= 10.1137/1.9781611976465.45 \|isbn=978-1-61197-646-5 \|s2cid=198968052 }}
	*{{cite journal \|~~first~~=Alan \|~~last~~=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}		*{{cite journal \|first1=Alan \|last1=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001\|osti=5686483 }}
	*{{citation\|~~first~~=P.\|~~last~~=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}		*{{citation\|first1=P.\|last1=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}
	*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}		*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}
	*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}		*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
	*{{cite journal \|~~first~~=W. F. \|~~last~~=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first1=W. F. \|last1=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

← Previous revision		Revision as of 00:37, 7 August 2022
Line 13:		Line 13:
	of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with ''n'' vertices, with vertices ''i'' and ''j'' connected by an edge when <math>a_{ij} \ne 0</math>, and the ''degree'' is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.		of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with ''n'' vertices, with vertices ''i'' and ''j'' connected by an edge when <math>a_{ij} \ne 0</math>, and the ''degree'' is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.

	A version of the minimum degree algorithm was implemented in the [[MATLAB]] function '''symmmd''' (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function '''symamd''', which is faster. This is confirmed by theoretical analysis, which shows that for graphs on ''n'' vertices and ''m'' edges, MMD has a tight [[Big O notation\|upper bound]] of <math>O(n^2m)</math> on its ~~run~~ time, whereas for AMD a tight bound of <math>O(nm)</math> holds.		A version of the minimum degree algorithm was implemented in the [[MATLAB]] function '''symmmd''' (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function '''symamd''', which is faster. This is confirmed by theoretical analysis, which shows that for graphs with ''n'' vertices and ''m'' edges, MMD has a tight [[Big O notation\|upper bound]] of <math>O(n^2m)</math> on its running time, whereas for AMD a tight bound of <math>O(nm)</math> holds. Cummings, Fahrbach, and Fatehpuria designed an exact minimum degree algorithm with <math>O(nm)</math> running time, and showed that no such algorithm can exist that runs in time <math>O(nm^{1-\varepsilon})</math>, for any <math>\varepsilon > 0</math>, assuming the [[strong exponential time hypothesis]].

	==References==		==References==
			*{{cite journal \|first=Robert \|last=Cummings \|first2=Matthew \|last2=Fahrbach \|first3=Animesh \|last3=Fatehpuria \|title=A fast minimum degree algorithm and matching lower bound \|journal=Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms \|year=2021 \|pages=724-734 \|doi= 10.1137/1.9781611976465.45 }}
			*{{cite journal \|first=Alan \|last=George \|first2=Joseph \|last2=Liu \|title=The evolution of the minimum degree ordering algorithm \|journal=[[SIAM Review]] \|volume=31 \|issue=1 \|pages=1–19 \|year=1989 \|jstor=2030845 \|doi=10.1137/1031001}}
		⚫	*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}
	*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}		*{{cite journal \|authorlink=Harry Markowitz \|first=H. M. \|last=Markowitz \|title=The elimination form of the inverse and its application to linear programming \|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences\|Management Science]] \|volume=3 \|issue=3 \|pages=255–269 \|year=1957 \|jstor=2627454 \|doi=10.1287/mnsc.3.3.255\|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|archive-url=https://web.archive.org/web/20170924000209/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0604711 \|url-status=dead \|archive-date=September 24, 2017 }}
	*{{cite ~~journal~~ \|first=~~Alan~~ \|last=~~George~~ \|~~first2~~=~~Joseph~~ ~~\|last2=Liu~~ ~~\|title=The evolution~~ of the ~~Minimum~~ ~~Degree~~ ~~Ordering~~ ~~Algorithm~~ ~~\|journal=[[SIAM~~ ~~Review]]~~ ~~\|volume=31~~ \|~~issue~~=1 \|~~pages~~=~~1–19~~ \|year=~~1989~~ \|~~jstor~~=~~2030845~~ \|~~doi~~=~~10.1137/1031001~~}}		*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
	*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}		*{{cite journal \|first=W. F. \|last=Tinney \|first2=J. W. \|last2=Walker \|title=Direct solution of sparse network equations by optimally ordered triangular factorization \|journal=[[Proceedings of the IEEE\|Proc. IEEE]] \|volume=55 \|issue=11 \|pages=1801–1809 \|year=1967 \|doi=10.1109/PROC.1967.6011 }}
	*{{cite book \|first=D. J. \|last=Rose \|chapter=A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations \|title=Graph Theory and Computing \|editor-first=R. C. \|editor-last=Read \|location=New York \|publisher=Academic Press \|year=1972 \|pages=183–217 \|isbn=0-12-583850-6 }}
⚫	*{{citation\|first=P.\|last=Heggernes \| author1-link = Pinar Heggernes \|first2=S. C. \|last2=Eisenstat \|first3=G. \|last3= Kumfert\| first4=A. \|last4=Pothen \|date=~~December~~ 2001 \|title=The Computational Complexity of the Minimum Degree Algorithm \|type= Technical report \|url=https://www.cs.purdue.edu/homes/apothen/Papers/md-conf.pdf \|publisher=Institute for Computer Applications in Science and Engineering}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}