# Using the poly module

A new module has been added to matfaust version 3.1.x. Its name is poly and as expected it is dedicated to a kind of Fausts that are defined according to series of polynomials.
In this notebook we'll see how to use the main functions of this module then we'll introduce one precise use case with the action of exponential matrix on a vector / matrix.
NOTE: all the functions introduced in this notebook are available on GPU, using the 'dev', 'gpu' arguments.

## 1. The basis function

Firstly, the poly module allows to define a polynomial basis (aka FaustPoly) using the function matfaust.poly.basis. Currently, only Chebyshev polynomials are supported but other are yet to come. Below is the prototype of the function:
basis(L, K, basis_name, varargin)
NOTE: it is noteworthy that varargin contains the optional T0 argument, we'll come back to this point later.
In the next, we shall see a simple example but I let you consult the documentation by typing help matfaust.poly.basis to get more details (alternatively, this is the online doc).
For instance, if you want to instantiate a basis Faust of dimension K+1 (in the example below K=5) on L, which by the way must be a sparse matrix at least square (and most likely symmetric positive definite in much use cases), you'll make this call to the function:
import matfaust.poly.basis
d = 128;
L = sprand(d, d, .2);
L = L*L';
K = 5;
F = basis(L, K, 'chebyshev')
F =
Faust size 768x128, density 0.847371, nnz_sum 83300, 6 factor(s): - FACTOR 0 (real) SPARSE, size 768x640, density 0.0344157, nnz 16916 - FACTOR 1 (real) SPARSE, size 640x512, density 0.0512329, nnz 16788 - FACTOR 2 (real) SPARSE, size 512x384, density 0.0847371, nnz 16660 - FACTOR 3 (real) SPARSE, size 384x256, density 0.168172, nnz 16532 - FACTOR 4 (real) SPARSE, size 256x128, density 0.496704, nnz 16276 - FACTOR 5 (real) SPARSE, size 128x128, density 0.0078125, nnz 128 identity matrix flag
As you can see, the last factor is followed by the mention identity matrix flag. It means that this factor is the identity matrix. This is not suprising, because the 0-degree Chebyshev polynomial is the identity. However, note that the T0 optional argument of the function is here to trick the basis by using another matrix than the identity even if eventually it might not be a proper basis it can be useful if you want to apply this basis on a vector or a matrix (hence you'll set T0 as this vector/matrix instead of multiplying the basis by this vector/matrix).
So how should we understand this Faust? You can see it as a vertical concatenation of polynomials. Indeed, the basis is composed of K+1 polynomials, the 0-degree polynomial is at the top of the stack (i.e. F(1:d,:) is the identity):
full(F(1:d, :))
ans = 128×128
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
This first 0-degree polynomial is followed by the next degree polynomials: hence F(d+1:d*2, :) is the 1-degree polynomial, F(d*2+1:d*3, :) is the 2-degree polynomial and so on...
For details about the Chebyshev polynomials, including their definition by a recurrence relationship (that is used here behind the scene), you can look at this wikipedia article.
One of the most important thing to note about a polynomial basis Faust is that the multiplication by a vector or a matrix is specialized in order to optimize the performance obtained compared to the generic Faust-vector/matrix multiplication. Indeed, due to the particular structure of the polynomial basis Faust, the multiplication can be optimized.
Let's verify that is true! In the code below F is cloned to a classic Faust G and the time of the multiplication by a matrix is measured in the both cases (with F, the basis Faust and G its classic Faust copy). Note that Faust.clone function is not used because in this case it would return a polynomial basis Faust (after all that's the role of clone to preserve the Faust properties!). To get a classic Faust the only way is to copy the Faust factor by factor.
facs = {};
for i=1:numfactors(F)
facs = [facs {factors(F,i)}];
end
G = matfaust.Faust(facs);
X = rand(size(F, 2), 100);
timeit(@() F*X)
ans = 0.0132
timeit(@() G*X)
ans = 0.0221
Now let's verify the multiplication result is accurate:
err = norm(F*X-G*X)/norm(F*X)
err = 2.7722e-17
As you see it's alright.

## 2. The poly function

The second function of the matfaust.poly module is poly. This function purpose is to compute a linear combination of polynomials composing a polynomial basis / FaustPoly (it can also be viewed as a way to compute a polynomial). So passing the FaustPoly F and the linear combination coefficients (one per polynomial, in ascending degree order) you'll obtain:
import matfaust.poly.poly
coeffs = rand(K+1, 1)*100;
lc_F = poly(coeffs, F)
lc_F =
Faust size 128x128, density 5.1311, nnz_sum 84068, 7 factor(s): - FACTOR 0 (real) SPARSE, size 128x768, density 0.0078125, nnz 768 - FACTOR 1 (real) SPARSE, size 768x640, density 0.0344157, nnz 16916 - FACTOR 2 (real) SPARSE, size 640x512, density 0.0512329, nnz 16788 - FACTOR 3 (real) SPARSE, size 512x384, density 0.0847371, nnz 16660 - FACTOR 4 (real) SPARSE, size 384x256, density 0.168172, nnz 16532 - FACTOR 5 (real) SPARSE, size 256x128, density 0.496704, nnz 16276 - FACTOR 6 (real) SPARSE, size 128x128, density 0.0078125, nnz 128 identity matrix flag
To be explicit about lc_F let's show how to rebuild it manually using G (which again is a classic Faust equal to F).
lc_G = coeffs(1)*G(1:d,:)
lc_G =
Faust size 128x128, density 4.05957, nnz_sum 66512, 6 factor(s): - FACTOR 0 (real) SPARSE, size 128x640, density 0.0015625, nnz 128 - FACTOR 1 (real) SPARSE, size 640x512, density 0.0512329, nnz 16788 - FACTOR 2 (real) SPARSE, size 512x384, density 0.0847371, nnz 16660 - FACTOR 3 (real) SPARSE, size 384x256, density 0.168172, nnz 16532 - FACTOR 4 (real) SPARSE, size 256x128, density 0.496704, nnz 16276 - FACTOR 5 (real) SPARSE, size 128x128, density 0.0078125, nnz 128
for i=2:K+1
lc_G = lc_G+coeffs(i)*G(d*(i-1)+1:d*i, :);
end
error = norm(full(lc_F)-full(lc_G))/norm(full(lc_G))
error = 1.0137e-16
Here again the basis FaustPoly operation is optimized compared to the Faust one. Speaking of which, there is ways to do even more optimized because the poly function is kind of matrix type agnostic, or precisely, it accepts a FaustPoly or a full array as the basis argument. Doing with the latter an optimized implementation is used whose the memory footprint is smaller than the one consumed with a FaustPoly. It can be particulary efficient when the use cases (as we'll see in 3.) consist to apply a linear combination of F to a vector x as it's shown below.
x = rand(size(F, 2));
way1 = @() poly(coeffs, F)*x; % first way to do as we've done above
way2 = @() poly(coeffs, F*x); % second way to do (quicker than way1)
way3 = @() poly(coeffs, F, 'X', x); % third way to do (quicker than way1 too)
timeit(way1)
ans = 0.0337
timeit(way2)
ans = 0.0130
timeit(way3)
ans = 0.0255
Depending on the situation the way2 or way3 might be the quickest, but they are always both quicker than way1.
Just in case let's verify all ways give the same results.
err_way2 = norm(poly(coeffs,F)*x-poly(coeffs,F*x))/norm(poly(coeffs, F)*x)
err_way2 = 2.6314e-17
err_way3 = norm(poly(coeffs, F)*x-poly(coeffs, F, 'X', x))/norm(poly(coeffs, F)*x)
err_way3 = 2.6314e-17
All sounds good! We shall now introduce one use case of Chebyshev polynomial series in FAµST that allow to get interesting results. But a last thing to note before going ahead to the part 3. is that the function poly is a little more complicated that it looks like, for more details I invite you to consult the API documentation.

## 3. Computing the action of the exponential of a matrix on a vector

In the next, we'll see how to compute the action of the exponential matrix on a vector x. This function has been originally developed in pyfaust inspired by the scipy.sparse.linalg.expm_multiply function. To get a computation time comparison, please consult the pyfaust jupyter notebook.
Recalling that it consists to compute exp(tA)x without computing directly the exponential let's use the function.
import matfaust.poly.expm_multiply
S = sprand(1024, 1024, .002);
A = S*S'; % A must be symmetric positive definite
X = rand(size(A, 2), 1);
pts = linspace(-.5, -.2, 1000); % all t must be negative
y = expm_multiply(A, X, pts)
y = 1000×1024
0.4428 -0.1650 -0.0128 -0.0785 0.9582 0.4735 0.3201 -0.1899 0.1672 0.8484 0.3565 0.3985 0.0178 0.3882 0.2830 -0.0713 -0.1608 0.0966 0.1099 0.1194 0.1649 0.1118 0.1484 0.7558 0.3175 0.2315 0.0193 0.0953 0.6403 -0.1513 0.0168 0.3543 0.1125 0.2528 0.2033 0.5364 0.0092 -0.2256 0.0678 -0.2720 0.4734 0.6132 0.3867 0.0179 0.7434 0.2224 -0.0932 0.0388 -0.2210 0.5989 0.4429 -0.1650 -0.0128 -0.0785 0.9582 0.4737 0.3203 -0.1900 0.1673 0.8484 0.3567 0.3986 0.0178 0.3883 0.2831 -0.0713 -0.1607 0.0966 0.1100 0.1194 0.1650 0.1119 0.1484 0.7558 0.3175 0.2316 0.0193 0.0953 0.6403 -0.1512 0.0168 0.3544 0.1125 0.2529 0.2034 0.5365 0.0093 -0.2256 0.0678 -0.2719 0.4735 0.6132 0.3869 0.0179 0.7434 0.2226 -0.0932 0.0388 -0.2209 0.5990 0.4430 -0.1650 -0.0128 -0.0784 0.9582 0.4738 0.3205 -0.1900 0.1675 0.8484 0.3569 0.3987 0.0178 0.3885 0.2831 -0.0714 -0.1606 0.0966 0.1102 0.1194 0.1651 0.1120 0.1484 0.7558 0.3176 0.2316 0.0194 0.0954 0.6404 -0.1512 0.0168 0.3546 0.1125 0.2531 0.2034 0.5366 0.0094 -0.2255 0.0678 -0.2718 0.4735 0.6133 0.3871 0.0179 0.7434 0.2228 -0.0932 0.0388 -0.2209 0.5991 0.4431 -0.1650 -0.0127 -0.0783 0.9582 0.4740 0.3207 -0.1900 0.1676 0.8484 0.3570 0.3988 0.0178 0.3886 0.2832 -0.0714 -0.1605 0.0966 0.1104 0.1194 0.1653 0.1120 0.1484 0.7558 0.3176 0.2317 0.0194 0.0955 0.6404 -0.1511 0.0169 0.3547 0.1125 0.2532 0.2035 0.5367 0.0094 -0.2255 0.0678 -0.2717 0.4736 0.6133 0.3873 0.0179 0.7434 0.2229 -0.0932 0.0388 -0.2208 0.5991 0.4432 -0.1650 -0.0127 -0.0782 0.9582 0.4741 0.3208 -0.1900 0.1677 0.8484 0.3572 0.3988 0.0178 0.3887 0.2833 -0.0714 -0.1604 0.0966 0.1106 0.1194 0.1654 0.1121 0.1484 0.7558 0.3176 0.2318 0.0194 0.0956 0.6405 -0.1511 0.0169 0.3548 0.1125 0.2534 0.2036 0.5368 0.0095 -0.2255 0.0678 -0.2715 0.4736 0.6133 0.3875 0.0179 0.7434 0.2231 -0.0931 0.0388 -0.2208 0.5992 0.4433 -0.1650 -0.0127 -0.0781 0.9582 0.4743 0.3210 -0.1900 0.1678 0.8484 0.3574 0.3989 0.0178 0.3888 0.2833 -0.0714 -0.1602 0.0966 0.1107 0.1194 0.1655 0.1122 0.1484 0.7558 0.3177 0.2319 0.0195 0.0957 0.6405 -0.1510 0.0169 0.3549 0.1125 0.2535 0.2037 0.5368 0.0096 -0.2254 0.0679 -0.2714 0.4736 0.6133 0.3877 0.0179 0.7434 0.2233 -0.0931 0.0388 -0.2207 0.5993 0.4434 -0.1650 -0.0126 -0.0781 0.9582 0.4744 0.3212 -0.1900 0.1680 0.8485 0.3576 0.3990 0.0178 0.3889 0.2834 -0.0714 -0.1601 0.0966 0.1109 0.1194 0.1656 0.1123 0.1484 0.7558 0.3177 0.2320 0.0195 0.0958 0.6406 -0.1509 0.0169 0.3551 0.1125 0.2537 0.2037 0.5369 0.0097 -0.2254 0.0679 -0.2713 0.4737 0.6133 0.3879 0.0179 0.7434 0.2235 -0.0931 0.0388 -0.2207 0.5994 0.4435 -0.1650 -0.0126 -0.0780 0.9582 0.4745 0.3213 -0.1900 0.1681 0.8485 0.3578 0.3991 0.0178 0.3890 0.2835 -0.0715 -0.1600 0.0966 0.1111 0.1194 0.1658 0.1124 0.1484 0.7558 0.3178 0.2321 0.0195 0.0959 0.6406 -0.1509 0.0169 0.3552 0.1125 0.2538 0.2038 0.5370 0.0098 -0.2254 0.0679 -0.2711 0.4737 0.6133 0.3881 0.0179 0.7434 0.2237 -0.0931 0.0388 -0.2206 0.5995 0.4436 -0.1650 -0.0126 -0.0779 0.9582 0.4747 0.3215 -0.1900 0.1682 0.8485 0.3580 0.3992 0.0178 0.3892 0.2835 -0.0715 -0.1599 0.0966 0.1112 0.1194 0.1659 0.1124 0.1484 0.7558 0.3178 0.2322 0.0196 0.0960 0.6407 -0.1508 0.0169 0.3553 0.1125 0.2540 0.2039 0.5371 0.0099 -0.2253 0.0679 -0.2710 0.4737 0.6134 0.3882 0.0179 0.7434 0.2239 -0.0931 0.0388 -0.2206 0.5996 0.4438 -0.1650 -0.0126 -0.0778 0.9582 0.4748 0.3217 -0.1900 0.1684 0.8485 0.3582 0.3992 0.0178 0.3893 0.2836 -0.0715 -0.1598 0.0966 0.1114 0.1194 0.1660 0.1125 0.1484 0.7558 0.3178 0.2323 0.0196 0.0961 0.6407 -0.1508 0.0169 0.3555 0.1125 0.2542 0.2040 0.5372 0.0100 -0.2253 0.0679 -0.2709 0.4738 0.6134 0.3884 0.0179 0.7434 0.2241 -0.0931 0.0388 -0.2205 0.5997
For more details about the use and the limitations of expm_multiply please see the API documentation.
Thanks for reading this notebook! Many other are available at faust.inria.fr.
This live script has been executed using the following version of matfaust:
matfaust.version()
ans = '3.1.2'