Divide-and-conquer eigenvalue algorithm - Revision history

Shoiti.tsurukawa: Explain how to compute w with the value of beta and z

2024-06-24T12:10:57Z

Explain how to compute w with the value of beta and z

← Previous revision		Revision as of 12:10, 24 June 2024
Line 41:		Line 41:
	:<math>T = \begin{bmatrix} Q_{1} & \\ & Q_{2} \end{bmatrix} \left( \begin{bmatrix} D_{1} & \\ & D_{2} \end{bmatrix} + \beta z z^{T} \right) \begin{bmatrix} Q_{1}^{T} & \\ & Q_{2}^{T} \end{bmatrix}</math>		:<math>T = \begin{bmatrix} Q_{1} & \\ & Q_{2} \end{bmatrix} \left( \begin{bmatrix} D_{1} & \\ & D_{2} \end{bmatrix} + \beta z z^{T} \right) \begin{bmatrix} Q_{1}^{T} & \\ & Q_{2}^{T} \end{bmatrix}</math>

	The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix <math>D + w w^{T}</math>, where <math>D</math> is diagonal with distinct entries and <math>w</math> is any vector with nonzero entries.		The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix <math>D + w w^{T}</math>, where <math>D</math> is diagonal with distinct entries and <math>w</math> is any vector with nonzero entries. In this case <math>w = \sqrt{\|\beta\|}\cdot z</math>.

	The case of a zero entry is simple, since if w<sub>i</sub> is zero, (<math>e_i</math>,d<sub>i</sub>) is an eigenpair (<math>e_i</math> is in the standard basis) of <math>D + w w^{T}</math> since		The case of a zero entry is simple, since if w<sub>i</sub> is zero, (<math>e_i</math>,d<sub>i</sub>) is an eigenpair (<math>e_i</math> is in the standard basis) of <math>D + w w^{T}</math> since

BD2412: disambiguation no longer needed; target is no longer a disambiguation page, removed: {{disambiguation needed|date=April 2024}}

2024-06-18T13:28:06Z

disambiguation no longer needed; target is no longer a disambiguation page, removed: {{disambiguation needed|date=April 2024}}

← Previous revision		Revision as of 13:28, 18 June 2024
Line 2:		Line 2:
	{{Multiple issues\|		{{Multiple issues\|
	{{No footnotes\|date=May 2024}}		{{No footnotes\|date=May 2024}}
	{{More ~~sources~~ needed\|date=May 2024}}		{{More citations needed\|date=May 2024}}
	}}		}}

Line 58:		Line 58:
	This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.		This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.

	All general eigenvalue algorithms must be iterative,{{Citation needed\|date=April 2024}} and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]~~{{disambiguation needed\|date=April 2024}}~~ secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.		All general eigenvalue algorithms must be iterative,{{Citation needed\|date=April 2024}} and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]] secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.

	==Analysis==		==Analysis==

Dedhert.Jr: multiple issues: first off, there are no footnotes providing the connection with the sources below, and second, many areas that are not covered with the sources.

2024-05-13T16:33:46Z

multiple issues: first off, there are no footnotes providing the connection with the sources below, and second, many areas that are not covered with the sources.

← Previous revision		Revision as of 16:33, 13 May 2024
Line 1:		Line 1:
	{{Short description\|Algorithm on Hermitian matrices}}		{{Short description\|Algorithm on Hermitian matrices}}
			{{Multiple issues\|
			{{No footnotes\|date=May 2024}}
			{{More sources needed\|date=May 2024}}
			}}

	'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.		'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.

Macrakis: copyedit; reduce throat-clearing

2024-04-21T20:46:05Z

copyedit; reduce throat-clearing

Macrakis: Adding local short description: "Algorithm on Hermitian matrices", overriding Wikidata description "in computer science, a class of algorithms to find the eigenvalues of Hermitian matrices"

2024-04-21T20:40:42Z

Adding local short description: "Algorithm on Hermitian matrices", overriding Wikidata description "in computer science, a class of algorithms to find the eigenvalues of Hermitian matrices"

← Previous revision		Revision as of 20:40, 21 April 2024
Line 1:		Line 1:
			{{Short description\|Algorithm on Hermitian matrices}}
	'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.		'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.

AnomieBOT: Dating maintenance tags: {{Disambiguation needed}}

2024-04-21T18:20:59Z

Dating maintenance tags: {{Disambiguation needed}}

← Previous revision		Revision as of 18:20, 21 April 2024
Line 52:		Line 52:
	This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.		This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.

	All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]{{disambiguation needed}} secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.		All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]{{disambiguation needed\|date=April 2024}} secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.

	==Analysis==		==Analysis==

BD2412: {{disambiguation needed}}, replaced: nonlinear → nonlinear{{disambiguation needed}}

2024-04-21T18:00:40Z

{{disambiguation needed}}, replaced: nonlinear → nonlinear{{disambiguation needed}}

← Previous revision		Revision as of 18:00, 21 April 2024
Line 18:		Line 18:
	:[[Image:Almost block diagonal.png]]		:[[Image:Almost block diagonal.png]]

	The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>. Note that the remark about <math>T</math> being almost block diagonal is true regardless of how <math>n</math> is chosen (i.e., there are many ways to so decompose the matrix). However, it makes sense, from an efficiency standpoint, to choose <math>n \approx m/2</math>.		The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>. Note that the remark about <math>T</math> being almost block diagonal is true regardless of how <math>n</math> is chosen (i.e., there are many ways to so decompose the matrix). However, it makes sense, from an efficiency standpoint, to choose <math>n \approx m/2</math>.

	We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)\|rank-1]] correction:		We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)\|rank-1]] correction:
Line 52:		Line 52:
	This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.		This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.

	All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]] secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.		All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]{{disambiguation needed}} secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.

	==Analysis==		==Analysis==
Line 85:		Line 85:
	\| year = 1997}}.		\| year = 1997}}.
	* {{cite journal \|first1=J.J.M. \|last1=Cuppen \|title=A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem \|journal=[[Numerische Mathematik]] \|volume=36 \|pages=177–195 \|date=1981 \|issue=2 \|doi=10.1007/BF01396757 \|s2cid=120504744 }}		* {{cite journal \|first1=J.J.M. \|last1=Cuppen \|title=A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem \|journal=[[Numerische Mathematik]] \|volume=36 \|pages=177–195 \|date=1981 \|issue=2 \|doi=10.1007/BF01396757 \|s2cid=120504744 }}


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

2A02:6B6B:58D3:0:D010:5280:6178:94BC: /* Variants and implementation */Noted that a link should be provided. This should be specifically for the advertised implementation of the “high-quality parallel” algorithm, not just the name of the overall package.

2023-09-09T12:29:49Z

Variants and implementation: Noted that a link should be provided. This should be specifically for the advertised implementation of the “high-quality parallel” algorithm, not just the name of the overall package.

← Previous revision		Revision as of 12:29, 9 September 2023
Line 73:		Line 73:
	There exist specialized root-finding techniques for rational functions that may do better than the Newton-Raphson method in terms of both performance and stability. These can be used to improve the iterative part of the divide-and-conquer algorithm.		There exist specialized root-finding techniques for rational functions that may do better than the Newton-Raphson method in terms of both performance and stability. These can be used to improve the iterative part of the divide-and-conquer algorithm.

	The divide-and-conquer algorithm is readily [[Parallel algorithm\|parallelized]], and [[linear algebra]] computing packages such as [[LAPACK]] contain high-quality parallel implementations.		The divide-and-conquer algorithm is readily [[Parallel algorithm\|parallelized]], and [[linear algebra]] computing packages such as [[LAPACK]] contain high-quality parallel implementations.{{Citation needed\|date=September 2023}}

	==References==		==References==

Citation bot: Add: s2cid, doi, issue. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 518/3848

2023-03-26T11:29:58Z

Add: s2cid, doi, issue. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 518/3848

← Previous revision		Revision as of 11:29, 26 March 2023
Line 84:		Line 84:
	\| title = Applied Numerical Linear Algebra		\| title = Applied Numerical Linear Algebra
	\| year = 1997}}.		\| year = 1997}}.
	* {{cite journal \|first1=J.J.M. \|last1=Cuppen \|title=A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem \|journal=[[Numerische Mathematik]] \|volume=36 \|pages=177–195 \|date=1981 }}		* {{cite journal \|first1=J.J.M. \|last1=Cuppen \|title=A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem \|journal=[[Numerische Mathematik]] \|volume=36 \|pages=177–195 \|date=1981 \|issue=2 \|doi=10.1007/BF01396757 \|s2cid=120504744 }}

Antreprize: /* Divide */

2022-08-08T11:27:42Z

Divide

← Previous revision		Revision as of 11:27, 8 August 2022
Line 37:		Line 37:
	The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix <math>D + w w^{T}</math>, where <math>D</math> is diagonal with distinct entries and <math>w</math> is any vector with nonzero entries.		The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix <math>D + w w^{T}</math>, where <math>D</math> is diagonal with distinct entries and <math>w</math> is any vector with nonzero entries.

	If w<sub>i</sub> is zero, (<math>e_i</math>,d<sub>i</sub>) is an eigenpair of <math>D + w w^{T}</math> since		The case of a zero entry is simple, since if w<sub>i</sub> is zero, (<math>e_i</math>,d<sub>i</sub>) is an eigenpair (<math>e_i</math> is in the standard basis) of <math>D + w w^{T}</math> since
	<math>(D + w w^{T})e_i = De_i = d_i e_i</math>.		<math>(D + w w^{T})e_i = De_i = d_i e_i</math>.

← Previous revision		Revision as of 16:33, 13 May 2024
Line 1:		Line 1:
	{{Short description\|Algorithm on Hermitian matrices}}		{{Short description\|Algorithm on Hermitian matrices}}
			{{Multiple issues\|
			{{No footnotes\|date=May 2024}}
			{{More sources needed\|date=May 2024}}
			}}

	'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.		'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.

← Previous revision		Revision as of 20:46, 21 April 2024
Line 2:		Line 2:
	'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.		'''Divide-and-conquer eigenvalue algorithms''' are a class of [[eigenvalue algorithm]]s for [[Hermitian matrix\|Hermitian]] or [[real number\|real]] [[Symmetric matrix\|symmetric matrices]] that have recently (circa 1990s) become competitive in terms of [[Numerical stability\|stability]] and [[Computational complexity theory\|efficiency]] with more traditional algorithms such as the [[QR algorithm]]. The basic concept behind these algorithms is the [[Divide and conquer algorithm\|divide-and-conquer]] approach from [[computer science]]. An [[eigenvalue]] problem is divided into two problems of roughly half the size, each of these are solved [[Recursion\|recursively]], and the eigenvalues of the original problem are computed from the results of these smaller problems.

	~~Here~~ we ~~present~~ the ~~simplest~~ ~~version~~ of ~~a divide-and-conquer~~ algorithm~~, similar to the~~ ~~one~~ originally proposed by Cuppen in 1981. ~~Many~~ ~~details~~ ~~that~~ ~~lie outside the scope of this article will be omitted; however,~~ without ~~considering~~ ~~these details, the algorithm is not fully stable~~.		This article covers the basic idea of the algorithm as originally proposed by Cuppen in 1981, which is not numerically stable without additional refinements.

	==Background==		==Background==
Line 11:		Line 11:
	The eigenvalues and eigenvectors of <math>T</math> are simply those of <math>T_{1}</math> and <math>T_{2}</math>, and it will almost always be faster to solve these two smaller problems than to solve the original problem all at once. This technique can be used to improve the efficiency of many eigenvalue algorithms, but it has special significance to divide-and-conquer.		The eigenvalues and eigenvectors of <math>T</math> are simply those of <math>T_{1}</math> and <math>T_{2}</math>, and it will almost always be faster to solve these two smaller problems than to solve the original problem all at once. This technique can be used to improve the efficiency of many eigenvalue algorithms, but it has special significance to divide-and-conquer.

	For the rest of this article, we will assume the input to the divide-and-conquer algorithm is an <math>m \times m</math> real symmetric tridiagonal matrix <math>T</math>. ~~Although the~~ algorithm can be modified for Hermitian matrices~~, we do not give the details here~~.		For the rest of this article, we will assume the input to the divide-and-conquer algorithm is an <math>m \times m</math> real symmetric tridiagonal matrix <math>T</math>. The algorithm can be modified for Hermitian matrices.

	==Divide==		==Divide==
Line 19:		Line 19:
	:[[Image:Almost block diagonal.png]]		:[[Image:Almost block diagonal.png]]

	The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>. ~~Note that the remark about~~ <math>T</math> ~~being~~ almost block diagonal ~~is true~~ regardless of how <math>n</math> is chosen (i.~~e., there are many ways to so decompose the matrix). However, it makes sense,~~ ~~from~~ an efficiency ~~standpoint,~~ to choose <math>n \approx m/2</math>.		The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>. <math>T</math> is almost block diagonal regardless of how <math>n</math> is chosen. For efficiency we typically choose <math>n \approx m/2</math>.

	We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)\|rank-1]] correction:		We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)\|rank-1]] correction:
Line 53:		Line 53:
	This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.		This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.

	All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]{{disambiguation needed\|date=April 2024}} secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.		All general eigenvalue algorithms must be iterative,{{Citation needed\|date=April 2024}} and the divide-and-conquer algorithm is no different. Solving the [[nonlinear]]{{disambiguation needed\|date=April 2024}} secular equation requires an iterative technique, such as the [[Newton's method\|Newton–Raphson method]]. However, each root can be found in [[Big O notation\|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.

	==Analysis==		==Analysis==

	~~As is common for divide and conquer algorithms, we~~ will use the [[Master theorem (analysis of algorithms)\|master theorem for divide-and-conquer recurrences]] to analyze the running time. Remember that above we stated we choose <math>n \approx m/2</math>. We can write the [[recurrence relation]]:		W will use the [[Master theorem (analysis of algorithms)\|master theorem for divide-and-conquer recurrences]] to analyze the running time. Remember that above we stated we choose <math>n \approx m/2</math>. We can write the [[recurrence relation]]:
	:<math>T(m) = 2 \times T\left(\frac{m}{2}\right) + \Theta(m^{2})</math>		:<math>T(m) = 2 \times T\left(\frac{m}{2}\right) + \Theta(m^{2})</math>
	In the notation of the Master theorem, <math>a = b = 2</math> and thus <math>\log_{b} a = 1</math>. Clearly, <math>\Theta(m^{2}) = \Omega(m^{1})</math>, so we have		In the notation of the Master theorem, <math>a = b = 2</math> and thus <math>\log_{b} a = 1</math>. Clearly, <math>\Theta(m^{2}) = \Omega(m^{1})</math>, so we have
	:<math>T(m) = \Theta(m^{2})</math>		:<math>T(m) = \Theta(m^{2})</math>

	~~Remember that above~~ we pointed out that reducing a Hermitian matrix to tridiagonal form takes <math>\frac{4}{3}m^{3}</math> flops. This dwarfs the running time of the divide-and-conquer part, and at this point it is not clear what advantage the divide-and-conquer algorithm offers over the QR algorithm (which also takes <math>\Theta(m^{2})</math> flops for tridiagonal matrices).		Above, we pointed out that reducing a Hermitian matrix to tridiagonal form takes <math>\frac{4}{3}m^{3}</math> flops. This dwarfs the running time of the divide-and-conquer part, and at this point it is not clear what advantage the divide-and-conquer algorithm offers over the QR algorithm (which also takes <math>\Theta(m^{2})</math> flops for tridiagonal matrices).

	The advantage of divide-and-conquer comes when eigenvectors are needed as well. If this is the case, reduction to tridiagonal form takes <math>\frac{8}{3}m^{3}</math>, but the second part of the algorithm takes <math>\Theta(m^{3})</math> as well. For the QR algorithm with a reasonable target precision, this is <math>\approx 6 m^{3}</math>, whereas for divide-and-conquer it is <math>\approx \frac{4}{3}m^{3}</math>. The reason for this improvement is that in divide-and-conquer, the <math>\Theta(m^{3})</math> part of the algorithm (multiplying <math>Q</math> matrices) is separate from the iteration, whereas in QR, this must occur in every iterative step. Adding the <math>\frac{8}{3}m^{3}</math> flops for the reduction, the total improvement is from <math>\approx 9 m^{3}</math> to <math>\approx 4 m^{3}</math> flops.		The advantage of divide-and-conquer comes when eigenvectors are needed as well. If this is the case, reduction to tridiagonal form takes <math>\frac{8}{3}m^{3}</math>, but the second part of the algorithm takes <math>\Theta(m^{3})</math> as well. For the QR algorithm with a reasonable target precision, this is <math>\approx 6 m^{3}</math>, whereas for divide-and-conquer it is <math>\approx \frac{4}{3}m^{3}</math>. The reason for this improvement is that in divide-and-conquer, the <math>\Theta(m^{3})</math> part of the algorithm (multiplying <math>Q</math> matrices) is separate from the iteration, whereas in QR, this must occur in every iterative step. Adding the <math>\frac{8}{3}m^{3}</math> flops for the reduction, the total improvement is from <math>\approx 9 m^{3}</math> to <math>\approx 4 m^{3}</math> flops.