Jacobi eigenvalue algorithm - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-25T15:56:32Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 15:56, 25 May 2025
Line 7:		Line 7:
	\|volume=1846 \|issue=30 \|year=1846 \|pages=51–94		\|volume=1846 \|issue=30 \|year=1846 \|pages=51–94
	\|language=German		\|language=German
	\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal		\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 \|url-access=subscription }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal
	\|first1=G.H. \|last1=Golub \|author1-link=Gene H. Golub		\|first1=G.H. \|last1=Golub \|author1-link=Gene H. Golub
	\|first2=H.A. \|last2=van der Vorst\|author2-link=Henk van der Vorst		\|first2=H.A. \|last2=van der Vorst\|author2-link=Henk van der Vorst

CRau080: /* Applications for real symmetric matrices */ ce (adding missing dot)

2025-03-12T21:42:20Z

Applications for real symmetric matrices: ce (adding missing dot)

← Previous revision		Revision as of 21:42, 12 March 2025
Line 248:		Line 248:

	;Singular values		;Singular values
	:The singular values of a (square) matrix <math>A</math> are the square roots of the (non-negative) eigenvalues of <math> A^T A </math>. In case of a symmetric matrix <math>S</math> we have of <math> S^T S = S^2 </math>, hence the singular values of <math>S</math> are the absolute values of the eigenvalues of <math>S</math>		:The singular values of a (square) matrix <math>A</math> are the square roots of the (non-negative) eigenvalues of <math> A^T A </math>. In case of a symmetric matrix <math>S</math> we have of <math> S^T S = S^2 </math>, hence the singular values of <math>S</math> are the absolute values of the eigenvalues of <math>S</math>.

	;2-norm and spectral radius		;2-norm and spectral radius

CRau080: /* Cost */ better (at least consistent) typesetting of one expression

2025-03-12T21:41:35Z

Cost: better (at least consistent) typesetting of one expression

← Previous revision		Revision as of 21:41, 12 March 2025
Line 84:		Line 84:
	== Cost ==		== Cost ==

	Each Givens rotation can be done in O(''n'') steps when the pivot element ''p'' is known. However the search for ''p'' requires inspection of all ''N'' ≈ {{sfrac\|1\|2}} ''n''<sup>2</sup> off-diagonal elements, which means this search dominates the overall complexity and pushes the computational complexity of a sweep in the classical Jacobi algorithm to <math> O(n^4) </math>. Competing algorithms attain <math> O(n^3) </math> complexity for a full diagonalisation.		Each Givens rotation can be done in <math> O(n) </math> steps when the pivot element ''p'' is known. However the search for ''p'' requires inspection of all ''N'' ≈ {{sfrac\|1\|2}} ''n''<sup>2</sup> off-diagonal elements, which means this search dominates the overall complexity and pushes the computational complexity of a sweep in the classical Jacobi algorithm to <math> O(n^4) </math>. Competing algorithms attain <math> O(n^3) </math> complexity for a full diagonalisation.

	=== Caching row maximums ===		=== Caching row maximums ===

Brightlightshine: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-02-27T09:40:29Z

Link suggestions feature: 3 links added.

← Previous revision		Revision as of 09:40, 27 February 2025
Line 56:		Line 56:
	== Convergence ==		== Convergence ==

	If <math> p = S_{kl} </math> is a pivot element, then by definition <math> \|S_{ij} \| \le \|p\| </math> for <math> 1 \le i, j \le n, i \ne j</math> . Let <math>\Gamma(S)^2</math> denote the sum of squares of all off-diagonal entries of <math>S</math>. Since <math>S</math> has exactly <math> 2N := n(n-1) </math> off-diagonal elements, we have <math> p^2 \le \Gamma(S )^2 \le 2 N p^2 </math> or <math> 2 p^2 \ge \Gamma(S )^2 / N </math> . Now <math>\Gamma(S^J)^2=\Gamma(S)^2-2p^2</math>. This implies		If <math> p = S_{kl} </math> is a [[pivot element]], then by definition <math> \|S_{ij} \| \le \|p\| </math> for <math> 1 \le i, j \le n, i \ne j</math> . Let <math>\Gamma(S)^2</math> denote the sum of squares of all off-diagonal entries of <math>S</math>. Since <math>S</math> has exactly <math> 2N := n(n-1) </math> off-diagonal elements, we have <math> p^2 \le \Gamma(S )^2 \le 2 N p^2 </math> or <math> 2 p^2 \ge \Gamma(S )^2 / N </math> . Now <math>\Gamma(S^J)^2=\Gamma(S)^2-2p^2</math>. This implies
	<math> \Gamma(S^J )^2 \le (1 - 1 / N ) \Gamma (S )^2 </math> or <math> \Gamma (S^ J ) \le (1 - 1 / N )^{1 / 2} \Gamma(S ) </math>;		<math> \Gamma(S^J )^2 \le (1 - 1 / N ) \Gamma (S )^2 </math> or <math> \Gamma (S^ J ) \le (1 - 1 / N )^{1 / 2} \Gamma(S ) </math>;
	that is, the sequence of Jacobi rotations converges at least linearly by a factor <math> (1 - 1 / N )^{1 / 2} </math> to a diagonal matrix.		that is, the sequence of Jacobi rotations converges at least linearly by a factor <math> (1 - 1 / N )^{1 / 2} </math> to a [[diagonal matrix]].

	A number of <math> N </math> Jacobi rotations is called a sweep; let <math> S^{\sigma} </math> denote the result. The previous estimate yields		A number of <math> N </math> Jacobi rotations is called a sweep; let <math> S^{\sigma} </math> denote the result. The previous estimate yields
Line 94:		Line 94:
	An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last=Wilkinson \|first=J.H. \|authorlink=James H. Wilkinson \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300\|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22\|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.		An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last=Wilkinson \|first=J.H. \|authorlink=James H. Wilkinson \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300\|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22\|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for [[disjoint sets]] of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.

	Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.		Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.

CRau080: adding authorlink fields to several ref.s

2025-02-23T22:11:19Z

adding authorlink fields to several ref.s

← Previous revision		Revision as of 22:11, 23 February 2025
Line 8:		Line 8:
	\|language=German		\|language=German
	\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal		\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal
	\|first1=G.H. \|last1=Golub		\|first1=G.H. \|last1=Golub \|author1-link=Gene H. Golub
	\|first2=H.A. \|last2=van der Vorst		\|first2=H.A. \|last2=van der Vorst\|author2-link=Henk van der Vorst
	\|title=Eigenvalue computation in the 20th century		\|title=Eigenvalue computation in the 20th century
	\|journal=Journal of Computational and Applied Mathematics		\|journal=Journal of Computational and Applied Mathematics
Line 65:		Line 65:

	However the following result of [[Arnold Schönhage\|Schönhage]]<ref>{{cite journal		However the following result of [[Arnold Schönhage\|Schönhage]]<ref>{{cite journal
	\|last=Schönhage \|first=A.		\|last=Schönhage \|first=A.\|authorlink=Arnold Schönhage
	\|title=Zur quadratischen Konvergenz des Jacobi-Verfahrens		\|title=Zur quadratischen Konvergenz des Jacobi-Verfahrens
	\|journal=Numerische Mathematik		\|journal=Numerische Mathematik
Line 92:		Line 92:

	=== Cyclic and parallel Jacobi ===		=== Cyclic and parallel Jacobi ===
	An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|~~last1~~=Wilkinson \|~~first1~~=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300\|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22\|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.		An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last=Wilkinson \|first=J.H. \|authorlink=James H. Wilkinson \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300\|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22\|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.

Cornmazes at 04:51, 25 December 2024

2024-12-25T04:51:25Z

← Previous revision		Revision as of 04:51, 25 December 2024
Line 1:		Line 1:
			{{short description\|Numerical linear algebra algorithm}}
	In [[numerical linear algebra]], the '''Jacobi eigenvalue algorithm''' is an [[iterative method]] for the calculation of the [[eigenvalue]]s and [[eigenvector]]s of a [[real number\|real]] [[symmetric matrix]] (a process known as [[Matrix diagonalization#Diagonalization\|diagonalization]]). It is named after [[Carl Gustav Jacob Jacobi]], who first proposed the method in 1846,<ref>{{cite journal		In [[numerical linear algebra]], the '''Jacobi eigenvalue algorithm''' is an [[iterative method]] for the calculation of the [[eigenvalue]]s and [[eigenvector]]s of a [[real number\|real]] [[symmetric matrix]] (a process known as [[Matrix diagonalization#Diagonalization\|diagonalization]]). It is named after [[Carl Gustav Jacob Jacobi]], who first proposed the method in 1846,<ref>{{cite journal
	\|last=Jacobi \|first=C.G.J. \|authorlink=Carl Gustav Jacob Jacobi		\|last=Jacobi \|first=C.G.J. \|authorlink=Carl Gustav Jacob Jacobi

Citation bot: Added doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical linear algebra | #UCB_Category 14/123

2024-12-21T05:34:22Z

Added doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical linear algebra | #UCB_Category 14/123

← Previous revision		Revision as of 05:34, 21 December 2024
Line 91:		Line 91:

	=== Cyclic and parallel Jacobi ===		=== Cyclic and parallel Jacobi ===
	An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300}}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22}}</ref> just like the classical Jacobi.		An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300\|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22\|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.

90.144.129.34: /* Cyclic and parallel Jacobi */ Removed duplicate word.

2024-12-06T22:06:25Z

Cyclic and parallel Jacobi: Removed duplicate word.

← Previous revision		Revision as of 22:06, 6 December 2024
Line 93:		Line 93:
	An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300}}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22}}</ref> just like the classical Jacobi.		An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300}}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22}}</ref> just like the classical Jacobi.

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.

	Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.		Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.

90.144.129.34: /* Cyclic and parallel Jacobi */ Removed duplicated text.

2024-12-06T22:01:57Z

Cyclic and parallel Jacobi: Removed duplicated text.

← Previous revision		Revision as of 22:01, 6 December 2024
Line 94:		Line 94:

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.
	The particular parallelisation of Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that both can be applied in parallel.

	Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.		Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)\|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.

90.144.129.34: /* Cyclic and parallel Jacobi */ Rewording.

2024-12-06T21:58:23Z

Cyclic and parallel Jacobi: Rewording.

← Previous revision		Revision as of 21:58, 6 December 2024
Line 93:		Line 93:
	An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300}}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22}}</ref> just like the classical Jacobi.		An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal \|last1=Wilkinson \|first1=J.H. \|title=Note on the Quadratic Convergence of the Cyclic Jacobi Process \|journal=Numerische Mathematik \|date=1962 \|volume=6 \|pages=296–300}}</ref><ref>{{cite journal \|last1=van Kempen \|first1=H.P.M. \|title=On Quadratic Convergence of the Special Cyclic Jacobi Method \|journal=Numerische Mathematik \|date=1966 \|volume=9 \|pages=19–22}}</ref> just like the classical Jacobi.

	The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> ~~implies~~ <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.		The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.
	The particular parallelisation of Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that both can be applied in parallel.		The particular parallelisation of Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of indices commute, so that both can be applied in parallel.

← Previous revision		Revision as of 15:56, 25 May 2025
Line 7:		Line 7:
	\|volume=1846 \|issue=30 \|year=1846 \|pages=51–94		\|volume=1846 \|issue=30 \|year=1846 \|pages=51–94
	\|language=German		\|language=German
	\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal		\|doi=10.1515/crll.1846.30.51 \|s2cid=199546177 \|url-access=subscription }}</ref> but only became widely used in the 1950s with the advent of computers.<ref>{{cite journal
	\|first1=G.H. \|last1=Golub \|author1-link=Gene H. Golub		\|first1=G.H. \|last1=Golub \|author1-link=Gene H. Golub
	\|first2=H.A. \|last2=van der Vorst\|author2-link=Henk van der Vorst		\|first2=H.A. \|last2=van der Vorst\|author2-link=Henk van der Vorst

← Previous revision		Revision as of 04:51, 25 December 2024
Line 1:		Line 1:
			{{short description\|Numerical linear algebra algorithm}}
	In [[numerical linear algebra]], the '''Jacobi eigenvalue algorithm''' is an [[iterative method]] for the calculation of the [[eigenvalue]]s and [[eigenvector]]s of a [[real number\|real]] [[symmetric matrix]] (a process known as [[Matrix diagonalization#Diagonalization\|diagonalization]]). It is named after [[Carl Gustav Jacob Jacobi]], who first proposed the method in 1846,<ref>{{cite journal		In [[numerical linear algebra]], the '''Jacobi eigenvalue algorithm''' is an [[iterative method]] for the calculation of the [[eigenvalue]]s and [[eigenvector]]s of a [[real number\|real]] [[symmetric matrix]] (a process known as [[Matrix diagonalization#Diagonalization\|diagonalization]]). It is named after [[Carl Gustav Jacob Jacobi]], who first proposed the method in 1846,<ref>{{cite journal
	\|last=Jacobi \|first=C.G.J. \|authorlink=Carl Gustav Jacob Jacobi		\|last=Jacobi \|first=C.G.J. \|authorlink=Carl Gustav Jacob Jacobi