What is BLAS?

Basic Linear Algebra Subprograms(BLAS) is a set of low-level routines for linear algebra operations. Most of the numerical libraries like NumPy and R do their linear algebra computations based on these standard operations. BLAS is often optimized for specific hardware for better performance; thus, BLAS has numerous different implementations depending on the vendor or type of processing unit(CPU/GPU).

Operations in BLAS are categorized into three levels based on their complexity.

Level 1: Vector operations

$O(n)$ operations on $O(n)$ operands

ex)  axpy, “a x plus y” $$y\leftarrow \alpha x+y$$

where $x,y\in {\mathbb{R}}^n$ and $\alpha \in \mathbb{R}$. $x,y$ are $n$-dimensional vectors each, hence we have $2n$ numbers. $\alpha$ is a scalar, hence we have $2n+1$ numbers in total. $$y_i=\alpha \times x_i+y_i\text{for }i=1,...,n$$ We have two floating point operations($1$ multiply and $1$ add) for each $i$ and we have to repeat it for $n$ times, thus we have $2n$ floating point operations in total.

In summary,
$2n+1$ numbers $\to O(n)$ operands
$2n$ floating point operations $\to O(n)$ operations

Level 2: Matrix-vector operations

$O(n^2)$ operations on $O(n^2)$ operands

ex) gemv, “generalized matrix-vector multiplication” $$y\leftarrow \alpha Ax+\beta y$$ where $A\in {\mathbb{R}}^{n\times n}$, $x,y\in {\mathbb{R}}^n$ and $\alpha ,\beta \in \mathbb{R}$.

$$y_i=\alpha \times \sum _j{A}_{ij}\times x_j+\beta \times y_i\text{for }i=1,...,n$$

Here, $A$ has $n^2$ numbers, $x,y$ has $n$ numbers each, thus we have $n^2+2n+2$ numbers.
For each $i$, we have $n+2$ multiplies and $(n-1)+1$ adds, hence $n(2n+2)=2n^2+2n$ FP_OPs.

In summary,
$n^2+2n+2$ numbers $\to O(n^2)$ operands
$2n^2+2n$ floating point operations $\to O(n^2)$ operations

Level 3 Matrix-matrix operations

$O(n^3)$ operations on $O(n^2)$ operands

ex) gemm, “generalized matrix multiplication” $$C\leftarrow \alpha AB+\beta C$$

where $A,B,C\in {\mathbb{R}}^{n\times n}$, and $\alpha ,\beta \in \mathbb{R}$.

$$C_{ij}=\alpha \times \sum _k{A}_{ik}\times B_{kj}+\beta \times C_{ij}\text{for }i,j=1,...,n$$ Here, $A,B,C$ has $n^2$ numbers each, thus we have $3n^2+2$ numbers.
For each $i$ and $j$, we have $n+2$ multiplies and $(n-1)+1$ adds, hence $n^2(2n+2)=2n^3+2n^2$ FP_OPs.

In summary,
$3n^2+2$ numbers $\to O(n^2)$ operands
$2n^3+2n^2$ floating point operations $\to O(n^3)$ operations