text:
an encyclopedia of finite element definitions

# Serendipity

 Abbreviated names S Orders $$1\leqslant k$$ Reference elements interval, quadrilateral, hexahedron Polynomial set $$\mathcal{P}_{k} \oplus \mathcal{X}_{k}$$↓ Show polynomial set definitions ↓ DOFs On each vertex: point evaluations On each edge: integral moments with an order $$k-2$$ dPc space On each face: integral moments with an order $$k-4$$ dPc space On each volume: integral moments with an order $$k-6$$ dPc space Number of DOFs interval: $$k+1$$ (A000027)quadrilateral: $$\begin{cases}4&k=1\\k(k+3)/2+3&k>1\end{cases}$$ (A340266)hexahedron: $$\begin{cases}12k-4&k=1,2,3\\3k^2-3k+14&k=4,5\\k(k-1)(k+1)/6+k^2+5k+4&k>6\end{cases}$$ Categories Scalar-valued elements

## Implementations

 Symfem string "serendipity"↓ Show Symfem examples ↓ Basix string "Serendipity"↓ Show Basix examples ↓ UFL string "S"↓ Show UFL examples ↓

## Examples

interval
order 1
interval
order 2
interval
order 3
order 1
order 2
order 3
• $$R$$ is the reference interval. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$
• $$\mathcal{L}=\{l_0,...,l_{1}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0)$$

$$\displaystyle \phi_{0} = 1 - x$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1)$$

$$\displaystyle \phi_{1} = x$$

This DOF is associated with vertex 1 of the reference element.
• $$R$$ is the reference interval. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$, $$x^{2}$$
• $$\mathcal{L}=\{l_0,...,l_{2}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0)$$

$$\displaystyle \phi_{0} = 3 x^{2} - 4 x + 1$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1)$$

$$\displaystyle \phi_{1} = x \left(3 x - 2\right)$$

This DOF is associated with vertex 1 of the reference element.
$$\displaystyle l_{2}:v\mapsto\displaystyle\int_{R}(1)v$$

$$\displaystyle \phi_{2} = 6 x \left(1 - x\right)$$

This DOF is associated with edge 0 of the reference element.
• $$R$$ is the reference interval. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$, $$x^{2}$$, $$x^{3}$$
• $$\mathcal{L}=\{l_0,...,l_{3}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0)$$

$$\displaystyle \phi_{0} = - 10 x^{3} + 18 x^{2} - 9 x + 1$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1)$$

$$\displaystyle \phi_{1} = x \left(10 x^{2} - 12 x + 3\right)$$

This DOF is associated with vertex 1 of the reference element.
$$\displaystyle l_{2}:v\mapsto\displaystyle\int_{R}(1 - t_{0})v$$

$$\displaystyle \phi_{2} = 12 x \left(5 x^{2} - 8 x + 3\right)$$

This DOF is associated with edge 0 of the reference element.
$$\displaystyle l_{3}:v\mapsto\displaystyle\int_{R}(t_{0})v$$

$$\displaystyle \phi_{3} = 12 x \left(- 5 x^{2} + 7 x - 2\right)$$

This DOF is associated with edge 0 of the reference element.
• $$R$$ is the reference quadrilateral. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$, $$y$$, $$x y$$
• $$\mathcal{L}=\{l_0,...,l_{3}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0,0)$$

$$\displaystyle \phi_{0} = x y - x - y + 1$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1,0)$$

$$\displaystyle \phi_{1} = x \left(1 - y\right)$$

This DOF is associated with vertex 1 of the reference element.
$$\displaystyle l_{2}:v\mapsto v(0,1)$$

$$\displaystyle \phi_{2} = y \left(1 - x\right)$$

This DOF is associated with vertex 2 of the reference element.
$$\displaystyle l_{3}:v\mapsto v(1,1)$$

$$\displaystyle \phi_{3} = x y$$

This DOF is associated with vertex 3 of the reference element.
• $$R$$ is the reference quadrilateral. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$, $$x^{2}$$, $$y$$, $$x y$$, $$y^{2}$$, $$x y^{2}$$, $$x^{2} y$$
• $$\mathcal{L}=\{l_0,...,l_{7}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0,0)$$

$$\displaystyle \phi_{0} = - 3 x^{2} y + 3 x^{2} - 3 x y^{2} + 7 x y - 4 x + 3 y^{2} - 4 y + 1$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1,0)$$

$$\displaystyle \phi_{1} = x \left(- 3 x y + 3 x + 3 y^{2} - y - 2\right)$$

This DOF is associated with vertex 1 of the reference element.
$$\displaystyle l_{2}:v\mapsto v(0,1)$$

$$\displaystyle \phi_{2} = y \left(3 x^{2} - 3 x y - x + 3 y - 2\right)$$

This DOF is associated with vertex 2 of the reference element.
$$\displaystyle l_{3}:v\mapsto v(1,1)$$

$$\displaystyle \phi_{3} = x y \left(3 x + 3 y - 5\right)$$

This DOF is associated with vertex 3 of the reference element.
$$\displaystyle l_{4}:v\mapsto\displaystyle\int_{e_{0}}(1)v$$

$$\displaystyle \phi_{4} = 6 x \left(x y - x - y + 1\right)$$

This DOF is associated with edge 0 of the reference element.
$$\displaystyle l_{5}:v\mapsto\displaystyle\int_{e_{1}}(1)v$$

$$\displaystyle \phi_{5} = 6 y \left(x y - x - y + 1\right)$$

This DOF is associated with edge 1 of the reference element.
$$\displaystyle l_{6}:v\mapsto\displaystyle\int_{e_{2}}(1)v$$

$$\displaystyle \phi_{6} = 6 x y \left(1 - y\right)$$

This DOF is associated with edge 2 of the reference element.
$$\displaystyle l_{7}:v\mapsto\displaystyle\int_{e_{3}}(1)v$$

$$\displaystyle \phi_{7} = 6 x y \left(1 - x\right)$$

This DOF is associated with edge 3 of the reference element.
• $$R$$ is the reference quadrilateral. The following numbering of the subentities of the reference is used:
• $$\mathcal{V}$$ is spanned by: $$1$$, $$x$$, $$x^{2}$$, $$x^{3}$$, $$y$$, $$x y$$, $$x^{2} y$$, $$y^{2}$$, $$x y^{2}$$, $$y^{3}$$, $$x y^{3}$$, $$x^{3} y$$
• $$\mathcal{L}=\{l_0,...,l_{11}\}$$
• Functionals and basis functions:
$$\displaystyle l_{0}:v\mapsto v(0,0)$$

$$\displaystyle \phi_{0} = 10 x^{3} y - 10 x^{3} - 18 x^{2} y + 18 x^{2} + 10 x y^{3} - 18 x y^{2} + 17 x y - 9 x - 10 y^{3} + 18 y^{2} - 9 y + 1$$

This DOF is associated with vertex 0 of the reference element.
$$\displaystyle l_{1}:v\mapsto v(1,0)$$

$$\displaystyle \phi_{1} = x \left(- 10 x^{2} y + 10 x^{2} + 12 x y - 12 x - 10 y^{3} + 18 y^{2} - 11 y + 3\right)$$

This DOF is associated with vertex 1 of the reference element.
$$\displaystyle l_{2}:v\mapsto v(0,1)$$

$$\displaystyle \phi_{2} = y \left(- 10 x^{3} + 18 x^{2} - 10 x y^{2} + 12 x y - 11 x + 10 y^{2} - 12 y + 3\right)$$

This DOF is associated with vertex 2 of the reference element.
$$\displaystyle l_{3}:v\mapsto v(1,1)$$

$$\displaystyle \phi_{3} = x y \left(10 x^{2} - 12 x + 10 y^{2} - 12 y + 5\right)$$

This DOF is associated with vertex 3 of the reference element.
$$\displaystyle l_{4}:v\mapsto\displaystyle\int_{e_{0}}(1 - t_{0})v$$

$$\displaystyle \phi_{4} = 12 x \left(- 5 x^{2} y + 5 x^{2} + 8 x y - 8 x - 3 y + 3\right)$$

This DOF is associated with edge 0 of the reference element.
$$\displaystyle l_{5}:v\mapsto\displaystyle\int_{e_{0}}(t_{0})v$$

$$\displaystyle \phi_{5} = 12 x \left(5 x^{2} y - 5 x^{2} - 7 x y + 7 x + 2 y - 2\right)$$

This DOF is associated with edge 0 of the reference element.
$$\displaystyle l_{6}:v\mapsto\displaystyle\int_{e_{1}}(1 - t_{0})v$$

$$\displaystyle \phi_{6} = 12 y \left(- 5 x y^{2} + 8 x y - 3 x + 5 y^{2} - 8 y + 3\right)$$

This DOF is associated with edge 1 of the reference element.
$$\displaystyle l_{7}:v\mapsto\displaystyle\int_{e_{1}}(t_{0})v$$

$$\displaystyle \phi_{7} = 12 y \left(5 x y^{2} - 7 x y + 2 x - 5 y^{2} + 7 y - 2\right)$$

This DOF is associated with edge 1 of the reference element.
$$\displaystyle l_{8}:v\mapsto\displaystyle\int_{e_{2}}(1 - t_{0})v$$

$$\displaystyle \phi_{8} = 12 x y \left(5 y^{2} - 8 y + 3\right)$$

This DOF is associated with edge 2 of the reference element.
$$\displaystyle l_{9}:v\mapsto\displaystyle\int_{e_{2}}(t_{0})v$$

$$\displaystyle \phi_{9} = 12 x y \left(- 5 y^{2} + 7 y - 2\right)$$

This DOF is associated with edge 2 of the reference element.
$$\displaystyle l_{10}:v\mapsto\displaystyle\int_{e_{3}}(1 - t_{0})v$$

$$\displaystyle \phi_{10} = 12 x y \left(5 x^{2} - 8 x + 3\right)$$

This DOF is associated with edge 3 of the reference element.
$$\displaystyle l_{11}:v\mapsto\displaystyle\int_{e_{3}}(t_{0})v$$

$$\displaystyle \phi_{11} = 12 x y \left(- 5 x^{2} + 7 x - 2\right)$$

This DOF is associated with edge 3 of the reference element.

## References

• Arnold, D. N. and Awanou, G. The serendipity family of finite elements, Foundations of Computational Mathematics 11(3), 337–344, 2011. [DOI: 10.1007/s10208-011-9087-3] [BibTeX]


text:
# Singular Values of Symmetric Matrix

I saw the following claim in this thread:

How to compute the SVD of a symmetric matrix?

Claim: The singular values of a symmetric matrix $$A$$ are the absolute values of its eigenvalues.

I understand why is it true for positive definite symmetric matrices as their be orthogonal diagonalization and SVD are the same.

But how can I prove it for a symmetric matrix which is not necessarily positive definite?

Let $$A=UDU^*$$ be the orthogonal diagonalization, where $$D = \mathrm{diag}(s_1,\dots,s_k,s_{k+1},\dots,s_n)$$ with $$s_1,\dots,s_k\geq 0$$ and $$s_{k+1},\dots,s_n<0$$.
Let $$V$$ be the matrix with the same firs $$k$$ columns as $$U$$ and the last $$n-k$$ columns which are the opposite as those of $$U$$: $$V=(u_1,\dots,u_k,-u_{k+1},\dots,-u_n),$$ where $$U=(u_1,\dots,u_n)$$. Moreover, let $$\Sigma = \mathrm{diag}(s_1,\dots,s_k,-s_{k+1},\dots,-s_n).$$ Then $$V$$ is also orthogonal and $$A=U\Sigma V^*$$ is the SVD of $$A$$.

format: plain


text:
# Randomized loose renaming in O(log log n) time

3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with $O( \log \log n )$ (individual) step complexity, where $n$ is a known upper bound on contention, and an adaptive algorithm with step complexity $O( (\log \log k)^2 )$, where $k$ is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires $O( k \log \log k )$ \emph{total} process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complement the algorithms with an $\Omega( \log \log n )$ expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use $O(n)$ test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.
Document type :
Conference papers

Cited literature [34 references]

https://hal.inria.fr/hal-00856744
Contributor : George Giakkoupis <>
Submitted on : Monday, September 2, 2013 - 1:55:51 PM
Last modification on : Tuesday, June 15, 2021 - 4:15:01 PM
Long-term archiving on: : Tuesday, December 3, 2013 - 5:16:09 AM

### File

podc13_renaming.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00856744, version 1

### Citation

Dan Alistarh, James Aspnes, George Giakkoupis, Philipp Woelfel. Randomized loose renaming in O(log log n) time. 32nd ACM Symposium on Principles of Distributed Computing (PODC), Jul 2013, Montreal, Canada. ⟨hal-00856744⟩

Record views


text:
# Nonnegative matrix factorization

(Difference between revisions)
 Revision as of 14:27, 28 September 2009 (edit)← Previous diff Current revision (17:40, 30 October 2016) (edit) (undo) (8 intermediate revisions not shown.) Line 1: Line 1: - Example from [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry], ch.4: + Exercise from [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry], ch.4: Given rank-2 nonnegative matrix Given rank-2 nonnegative matrix $X=\!\left[\!\begin{array}{ccc}17&28&42\\ [itex]X=\!\left[\!\begin{array}{ccc}17&28&42\\ 16&47&51\\ 16&47&51\\ - 17&82&72\end{array}\!\right],$ + 17&82&72\end{array}\!\right],[/itex] - + find a nonnegative factorization find a nonnegative factorization $X=WH\,$ $X=WH\,$ by solving by solving - $\begin{array}{cl}\mbox{find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ + [itex]\begin{array}{cl}{\text find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ - \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X\\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ + {\text subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &W\geq0\\ &H\geq0\\ &H\geq0\\ - &\mbox{rank}\,Z\leq2\end{array}$ + &{\text rank}\,Z\leq2\end{array}[/itex] which follows from the fact, at optimality, which follows from the fact, at optimality, - $Z^\star=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} + [itex] Z^*=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} \end{array}$ \end{array}[/itex] Use the known closed-form solution for a direction vector $Y\,$ to regulate rank (rank constraint is replaced) by [[Convex Iteration]]; Use the known closed-form solution for a direction vector $Y\,$ to regulate rank (rank constraint is replaced) by [[Convex Iteration]]; - set $_{}Z^\star\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^\mathbf{8}$ to an ordered diagonalization and + set $_{}Z^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}$ to a nonincreasingly ordered diagonalization and - $_{}U^\star\!=_{\!}Q(:\,,_{^{}}3\!:\!8)\!\in_{\!}\reals^{\mathbf{8}\times\mathbf{6}}$, + $_{}U^*\!=_{\!}Q(:\,,_{^{}}3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}$, - then $Y\!=U^\star U^{\star\rm T}.$ + then $Y\!=U^* U^{*\rm T}.$

Line 31: Line 30: $\begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ [itex]\begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ - \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X\\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ + \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &W\geq0\\ &H\geq0\end{array}$ &H\geq0\end{array}[/itex] Line 37: Line 36: with with - $Y\!=U^\star U^{\star\rm T}.$ + $Y\!=U^* U^{*\rm T}.$ + Global convergence occurs, in this example, in only a few iterations.

## Current revision

Exercise from Convex Optimization & Euclidean Distance Geometry, ch.4:

Given rank-2 nonnegative matrix $LaTeX: X=\!\left[\!\begin{array}{ccc}17&28&42\\

 16&47&51\\

17&82&72\end{array}\!\right],$

find a nonnegative factorization $LaTeX: X=WH\,$ by solving

$LaTeX: \begin{array}{cl}{\text find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ {\text subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &H\geq0\\ &{\text rank}\,Z\leq2\end{array}$

which follows from the fact, at optimality,

$LaTeX: Z^*=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} \end{array}$

Use the known closed-form solution for a direction vector $LaTeX: Y\,$ to regulate rank (rank constraint is replaced) by Convex Iteration;

set $LaTeX: _{}Z^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}$ to a nonincreasingly ordered diagonalization and $LaTeX: _{}U^*\!=_{\!}Q(:\,,_{^{}}3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}$, then $LaTeX: Y\!=U^* U^{*\rm T}.$

In summary, initialize $LaTeX: Y=I\,$ then alternate solution of

$LaTeX: \begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &H\geq0\end{array}$

with

$LaTeX: Y\!=U^* U^{*\rm T}.$ Global convergence occurs, in this example, in only a few iterations.