Random

Generating random numbers

In HighFM, the random numbers are generated in two steps. First, a RandomEngine (e.g., PCG ) creates a sequence of 64 pseudorandom bits. Generator then transforms these bits into a random number that follows a specific probability distribution (such as uniform and normal distributions).

HighFM implements three different pseudorandom generators:

Name	Type	Output (bits)	Period	Streams
PCG	LCG	64	\(2^{128}\)	\(2^{127}\)
SplitMix	Counter	64	\(2^{64}\)	\(2^{63}\)
Xoroshiro	LSFR	64	\(2^{256} - 1\)	1

• Generator
• PCG
• Xoroshiro
• SplitMix

Constructing a sketch operator

In the heart of the Randomized Linear algebra lies the sketching operator \(\mathbf{S} \in \mathbb{C}^{\ell \times n}\) with \(\ell \ll n\) that distorts the Euclidean norm \(\| \cdot \|_2\) in a controlled manner [1]. Formally, for a \(\gamma \in [0, 1)\) and a subspace \(\mathbb{F}^n \subset \mathbb{C}^n\), then \(\mathbf{S}\) is a linear map that satisfies

\[(1 - \gamma) \|\vec{x}\| \leq \|\mathbf{S}\vec{x}\| \leq (1 +\gamma) \|\vec{x}\|, \quad \forall \vec{x} \in \mathbb{F}^n\]

In this case, we say that \(\mathbf{S}\) is a embedding of \(\mathbb{F}^n\) with a distortion \(\gamma\). In pratice, the matrix \(\mathbf{S}\) is not explicitly available and we use random distributions to achieve the relation above with high probability. See [1] for more details.

HighFM currently supports the following sketching operators:

• Gaussian Sketching
• Sparse Sign Sketching
• SRTT Sketching

References

[1] (1,2)

P.-G. Martinsson and J. A. Tropp, “Randomized numerical linear algebra: Foundations and algorithms”, Acta Numerica, vol. 29, pp. 403–572, May 2020, doi: 10.1017/S0962492920000021.