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 |
---|---|---|---|---|
LCG |
64 |
\(2^{128}\) |
\(2^{127}\) |
|
Counter |
64 |
\(2^{64}\) |
\(2^{63}\) |
|
LSFR |
64 |
\(2^{256} - 1\) |
1 |
API¶
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
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. The idea is to use this sketching operator to reduce the dimensionality of the problem, improving its performance. See [1] for more details.
HighFM currently supports the following sketching operators: