Description

In this demo we will look at the cost of a sparse matrix-vector multipy ($A * v$) for different sparse matrix formats.

from pyamg import gallery
import numpy as np
from time import time
import matplotlib.pyplot as plt
%matplotlib inline

Set up problem sizes

Set up the tests to do ntrials of $w \leftarrow A * v$ at different sizes in nlist with nnzperrow non-zeros per row on average

types = ['csr', 'coo', 'csc', 'lil']
k = np.arange(1, 10)
nv = np.array([1e2, 1e3])
nlist = np.kron(nv, k)
ntrials = 10
nnzperrow = 50

set up containers

times = {a: np.zeros((len(nlist), ntrials)) for a in types}
A = {a: [] for a in types}
nnz = []

create matrix and time it

for j, n in enumerate(nlist):
    print("n = %d" % n)
    tmp = time()
    A['csr'] = gallery.sprand(n, n, float(nnzperrow) / n, format='csr')
    tmp = time() - tmp
    print("    setup: %g" % tmp)
    v = np.random.rand(n,)
    w = 0 * v.copy()
    for tp in types:
        if tp is 'csr':
            nnz.append(A[tp].nnz)
        if tp is not 'csr':
            A[tp] = getattr(A['csr'], 'to' + tp)()
        for i in range(ntrials):
            tmp = time()
            w = A[tp] * v
            tmp = time() - tmp
            times[tp][j, i] = tmp
        print("    mat-vec %s: %g" % (tp, tmp))

n = 100
    setup: 0.00209284
    mat-vec csr: 8.82149e-06
    mat-vec coo: 2.21729e-05
    mat-vec csc: 9.05991e-06
    mat-vec lil: 0.000833988
n = 200
    setup: 0.00146484
    mat-vec csr: 1.28746e-05
    mat-vec coo: 2.5034e-05
    mat-vec csc: 1.50204e-05
    mat-vec lil: 0.000884056
n = 300
    setup: 0.00269198
    mat-vec csr: 1.88351e-05
    mat-vec coo: 6.8903e-05
    mat-vec csc: 2.09808e-05
    mat-vec lil: 0.00134301
n = 400
    setup: 0.00206494
    mat-vec csr: 2.31266e-05
    mat-vec coo: 4.69685e-05
    mat-vec csc: 2.40803e-05
    mat-vec lil: 0.00181985
n = 500
    setup: 0.00281
    mat-vec csr: 2.59876e-05
    mat-vec coo: 9.20296e-05
    mat-vec csc: 2.88486e-05
    mat-vec lil: 0.00316596
n = 600
    setup: 0.00375104
    mat-vec csr: 2.90871e-05
    mat-vec coo: 6.79493e-05
    mat-vec csc: 3.31402e-05
    mat-vec lil: 0.00310707
n = 700
    setup: 0.00467706
    mat-vec csr: 3.29018e-05
    mat-vec coo: 7.79629e-05
    mat-vec csc: 3.69549e-05
    mat-vec lil: 0.00384092
n = 800
    setup: 0.00578094
    mat-vec csr: 3.69549e-05
    mat-vec coo: 9.39369e-05
    mat-vec csc: 4.22001e-05
    mat-vec lil: 0.0044229
n = 900
    setup: 0.00604796
    mat-vec csr: 4.1008e-05
    mat-vec coo: 9.98974e-05
    mat-vec csc: 4.79221e-05
    mat-vec lil: 0.0052371
n = 1000
    setup: 0.00617695
    mat-vec csr: 4.50611e-05
    mat-vec coo: 0.000109911
    mat-vec csc: 5.00679e-05
    mat-vec lil: 0.00595903
n = 2000
    setup: 0.01191
    mat-vec csr: 8.39233e-05
    mat-vec coo: 0.000216007
    mat-vec csc: 9.48906e-05
    mat-vec lil: 0.0128779
n = 3000
    setup: 0.017545
    mat-vec csr: 0.000124931
    mat-vec coo: 0.000323057
    mat-vec csc: 0.000153065
    mat-vec lil: 0.0182021
n = 4000
    setup: 0.0224109
    mat-vec csr: 0.000167847
    mat-vec coo: 0.000432968
    mat-vec csc: 0.000190973
    mat-vec lil: 0.025667
n = 5000
    setup: 0.0333879
    mat-vec csr: 0.000230074
    mat-vec coo: 0.000565052
    mat-vec csc: 0.000259161
    mat-vec lil: 0.0413041
n = 6000
    setup: 0.045969
    mat-vec csr: 0.00135493
    mat-vec coo: 0.00113392
    mat-vec csc: 0.000375986
    mat-vec lil: 0.046416
n = 7000
    setup: 0.0470712
    mat-vec csr: 0.000710011
    mat-vec coo: 0.00247192
    mat-vec csc: 0.00127006
    mat-vec lil: 0.0461471
n = 8000
    setup: 0.0471659
    mat-vec csr: 0.000501871
    mat-vec coo: 0.00102901
    mat-vec csc: 0.000859976
    mat-vec lil: 0.049119
n = 9000
    setup: 0.0616531
    mat-vec csr: 0.000856876
    mat-vec coo: 0.00118303
    mat-vec csc: 0.000746012
    mat-vec lil: 0.060231

/usr/local/lib/python3.5/site-packages/ipykernel/__main__.py:7: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

Plot problem size (nnz) and times in log-log

nnz = np.array(nnz)
plt.figure(figsize=(12,12))
plt.hold(True)
for tp in types:
    plt.loglog(nlist, times[tp].min(axis=1), label=tp, lw=3)
plt.loglog(nlist, nnz / nnz[0] * times[types[0]][0, 0], label='nnz')
plt.legend()
plt.show()