Difference between revisions of "Main Page"
Borishaase (talk | contribs) m (RU-method) |
Borishaase (talk | contribs) (RU method) |
||
| Line 2: | Line 2: | ||
= Welcome to MWiki = | = Welcome to MWiki = | ||
== Theorem of the month == | == Theorem of the month == | ||
| − | === RU | + | === 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 (RU | + | 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 (RU 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 10: | Line 10: | ||
If <math>a_{jk} \le 0</math> is given for at least one couple <math>(j, k)</math> and <math>A := (a_{jk})</math>, then compute the sums <math>s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j}</math> for an arbitrary transcendental number <math>\varepsilon</math> and <math>s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0</math> for all <math>k</math>. Replace <math>x_k</math> by <math>-x_k</math> for <math>s_k < 0</math>. Then add a multiple of <math>s^Tx</math> resp. <math>s_0</math> to <math>Ax = b</math>, such that now <math>a_{jk} > 0</math> holds for all <math>(j, k)</math>. From <math>D_j := (d_{jk}), d_{jk} = \delta_{jk}/\prod\limits_{m=1}^n{a_{jm}}</math> and <math>C_j := D_j R_j = (c_{jk})</math>, it follows that <math>x_j^\prime = (AC_jx^\prime)_j = (C_jb)_j</math> for the Kronecker delta <math>\delta_{jk}</math>. If, however, <math>x_j^\prime = 0 \ne b_j</math> holds for one <math>j</math>, the LS cannot be solved.<math>\square</math> | If <math>a_{jk} \le 0</math> is given for at least one couple <math>(j, k)</math> and <math>A := (a_{jk})</math>, then compute the sums <math>s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j}</math> for an arbitrary transcendental number <math>\varepsilon</math> and <math>s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0</math> for all <math>k</math>. Replace <math>x_k</math> by <math>-x_k</math> for <math>s_k < 0</math>. Then add a multiple of <math>s^Tx</math> resp. <math>s_0</math> to <math>Ax = b</math>, such that now <math>a_{jk} > 0</math> holds for all <math>(j, k)</math>. From <math>D_j := (d_{jk}), d_{jk} = \delta_{jk}/\prod\limits_{m=1}^n{a_{jm}}</math> and <math>C_j := D_j R_j = (c_{jk})</math>, it follows that <math>x_j^\prime = (AC_jx^\prime)_j = (C_jb)_j</math> for the Kronecker delta <math>\delta_{jk}</math>. If, however, <math>x_j^\prime = 0 \ne b_j</math> holds for one <math>j</math>, the LS cannot be solved.<math>\square</math> | ||
| + | '''Remark:''' Extending the theorem to complex numbers and over- or underdetermined LS is easy. | ||
== Recommended reading == | == Recommended reading == | ||
Revision as of 17:40, 5 November 2020
Welcome to MWiki
Theorem of the month
RU method
If the linear system (LS) [math]\displaystyle{ Ax = b \in {}^{\nu}\mathbb{Q}^{n} }[/math] can be uniquely solved for [math]\displaystyle{ n \in {}^{\nu}\mathbb{N}^* }[/math], the root of unity method (RU 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] sowie [math]\displaystyle{ n_{jk} := j + k - 3 }[/math] as well as [math]\displaystyle{ r_{1jk} := \hat{n}e^{i\tau n_{jk}/n} }[/math] both [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]. That implies obviously rk[math]\displaystyle{ (R_j) = n }[/math]. If [math]\displaystyle{ A(x - x^\prime) = (1 - x_j, ..., 1 - x_j)^T }[/math] and [math]\displaystyle{ Ax^\prime = b }[/math] imply [math]\displaystyle{ x_j = 1 }[/math] for all [math]\displaystyle{ j }[/math], then most likely rk[math]\displaystyle{ (A) = n }[/math].
If [math]\displaystyle{ a_{jk} \le 0 }[/math] is given for at least one couple [math]\displaystyle{ (j, k) }[/math] and [math]\displaystyle{ A := (a_{jk}) }[/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]. Then add a multiple of [math]\displaystyle{ s^Tx }[/math] resp. [math]\displaystyle{ s_0 }[/math] to [math]\displaystyle{ Ax = b }[/math], such that now [math]\displaystyle{ a_{jk} > 0 }[/math] holds for all [math]\displaystyle{ (j, k) }[/math]. From [math]\displaystyle{ D_j := (d_{jk}), d_{jk} = \delta_{jk}/\prod\limits_{m=1}^n{a_{jm}} }[/math] and [math]\displaystyle{ C_j := D_j R_j = (c_{jk}) }[/math], it follows that [math]\displaystyle{ x_j^\prime = (AC_jx^\prime)_j = (C_jb)_j }[/math] for the Kronecker delta [math]\displaystyle{ \delta_{jk} }[/math]. If, however, [math]\displaystyle{ x_j^\prime = 0 \ne b_j }[/math] holds for one [math]\displaystyle{ j }[/math], the LS cannot be solved.[math]\displaystyle{ \square }[/math]
Remark: Extending the theorem to complex numbers and over- or underdetermined LS is easy.