Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
m (RU method)
m (RU method)
Line 3: Line 3:
 
== Theorem of the month ==
 
== Theorem of the month ==
 
=== RU method ===
 
=== RU method ===
If the linear system (LS) <math>Ax = b \in  {}^{\nu}\mathbb{Q}^{n}</math> can be uniquely solved for <math>n \in {}^{\nu}\mathbb{N}^*</math>, the ''root of unity method (<math>RU</math> method)'' computes <math>x \in {}^{\nu}\mathbb{Q}^{n}</math> for <math>A \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math>.
+
If <math>A \in {}^{\nu}\mathbb{Q}^{n \times n}</math> is regular in the linear system (LS) <math>Ax = b \in  {}^{\nu}\mathbb{Q}^{n}</math> for <math>n \in {}^{\nu}\mathbb{N}^*</math>, the ''root of unity method (<math>RU</math> method)'' computes <math>x \in {}^{\nu}\mathbb{Q}^{n}</math> for <math>A \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math>.
  
 
=== Proof and algorithm ===
 
=== Proof and algorithm ===
Line 13: Line 13:
 
The RU method allows to determine every eigenvalue and -vector of <math>Ax = \lambda x \in {}^{\nu}\mathbb{Q}^{n} + {}^{\nu}\mathbb{Q}^{n}</math> for <math>n \in {}^{\nu}2\mathbb{N}^*, \lambda \in {}^{\nu}\mathbb{Q}+ {i}^{\nu}\mathbb{Q}</math> and <math>A  \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math> by putting <math>x^{\prime(\grave{m})} = C_j^{-1}AC_j x^{\prime(m)}</math>.
 
The RU method allows to determine every eigenvalue and -vector of <math>Ax = \lambda x \in {}^{\nu}\mathbb{Q}^{n} + {}^{\nu}\mathbb{Q}^{n}</math> for <math>n \in {}^{\nu}2\mathbb{N}^*, \lambda \in {}^{\nu}\mathbb{Q}+ {i}^{\nu}\mathbb{Q}</math> and <math>A  \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math> by putting <math>x^{\prime(\grave{m})} = C_j^{-1}AC_j x^{\prime(m)}</math>.
  
'''Remark:''' Extending the theorem to complex <math>A</math> and <math>b</math> is easy.
+
'''Remark:''' Extending the theorem to complex <math>A</math> and <math>b</math> is easy. By the Banach fixed-point theorem, the \(RU\) method converges linearly for every regular LS.
 
== Recommended reading ==
 
== Recommended reading ==
  

Revision as of 08:54, 18 November 2020

Welcome to MWiki

Theorem of the month

RU method

If [math]\displaystyle{ A \in {}^{\nu}\mathbb{Q}^{n \times n} }[/math] is regular in the linear system (LS) [math]\displaystyle{ Ax = b \in {}^{\nu}\mathbb{Q}^{n} }[/math] for [math]\displaystyle{ n \in {}^{\nu}\mathbb{N}^* }[/math], the root of unity method ([math]\displaystyle{ RU }[/math] method) computes [math]\displaystyle{ x \in {}^{\nu}\mathbb{Q}^{n} }[/math] for [math]\displaystyle{ A \in {}^{\nu}\mathbb{Q}^{n \times n} }[/math] in [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

Proof and algorithm

Let [math]\displaystyle{ R_1 := (r_{1jk}) = (r_{1kj}) = R_1^T \in {}^{\nu}\mathbb{C}^{n \times n}, n \in {}^{\nu}2\mathbb{N}^*, r_{11k} := 1 }[/math] and for [math]\displaystyle{ j > 1 }[/math] as well as [math]\displaystyle{ n_{jk} := j + k - 3 }[/math] both [math]\displaystyle{ r_{1jk} := \hat{n}e^{i\tau n_{jk}/n} }[/math] for [math]\displaystyle{ n_{jk} < n }[/math] and [math]\displaystyle{ r_{1jk} := \hat{n}e^{i\tau(n_{jk} - \acute{n})/n} }[/math] for [math]\displaystyle{ n_{jk} \ge n }[/math]. Interchanging the first and [math]\displaystyle{ j }[/math]-th row resp. column position and correspondingly interchanging the remaining row and column positions yields matrices [math]\displaystyle{ R_j = R_j^T }[/math] for [math]\displaystyle{ j > 1 }[/math]. Let [math]\displaystyle{ \delta_{jk} }[/math] be the Kronecker delta and [math]\displaystyle{ A := (a_{jk}) }[/math].

If [math]\displaystyle{ a_{jk} \le 0 }[/math] is given for at least one couple [math]\displaystyle{ (j, k) }[/math], then compute the sums [math]\displaystyle{ s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j} }[/math] for an arbitrary transcendental number [math]\displaystyle{ \varepsilon }[/math] and [math]\displaystyle{ s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0 }[/math] for all [math]\displaystyle{ k }[/math]. Replace [math]\displaystyle{ x_k }[/math] by [math]\displaystyle{ -x_k }[/math] for [math]\displaystyle{ s_k < 0 }[/math]. Add a multiple of [math]\displaystyle{ s^Tx }[/math] resp. [math]\displaystyle{ s_0 }[/math] to [math]\displaystyle{ Ax = b }[/math], such that [math]\displaystyle{ a_{jk} > 0 }[/math] holds for all [math]\displaystyle{ (j, k) }[/math]. Let [math]\displaystyle{ b_j = 1 }[/math] for all [math]\displaystyle{ j }[/math] wlog. For [math]\displaystyle{ D_j := (d_{jk}), d_{jk} = \delta_{jk}⁄a_{jk}, C_j := D_j R_j }[/math] and [math]\displaystyle{ x_k^{(0)} := \hat{n}/ \max_j a_{jk} }[/math], let [math]\displaystyle{ x^{(\grave{m})} = x^{(m)} + C_j^{-1}(b - Ax^{(m)}).\square }[/math]

Corollary

The RU method allows to determine every eigenvalue and -vector of [math]\displaystyle{ Ax = \lambda x \in {}^{\nu}\mathbb{Q}^{n} + {}^{\nu}\mathbb{Q}^{n} }[/math] for [math]\displaystyle{ n \in {}^{\nu}2\mathbb{N}^*, \lambda \in {}^{\nu}\mathbb{Q}+ {i}^{\nu}\mathbb{Q} }[/math] and [math]\displaystyle{ A \in {}^{\nu}\mathbb{Q}^{n \times n} }[/math] in [math]\displaystyle{ \mathcal{O}(n^2) }[/math] by putting [math]\displaystyle{ x^{\prime(\grave{m})} = C_j^{-1}AC_j x^{\prime(m)} }[/math].

Remark: Extending the theorem to complex [math]\displaystyle{ A }[/math] and [math]\displaystyle{ b }[/math] is easy. By the Banach fixed-point theorem, the \(RU\) method converges linearly for every regular LS.

Recommended reading

Nonstandard Mathematics