# Efficient multiplication of out-of-memory sparse matrix and an in-memory dense vector

**URL:** <https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663>\
**Category:** General Usage\
**Created:** [January 15, 2019, 3:29pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663 "2019-01-15T15:29:27Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 15, 2019, 3:29pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/1 "2019-01-15T15:29:27Z")

</div>

Say I have a really huge sparse matrix A, and an equally huge dense vector v. I need to do `A * v`. The structure of `A` is simple, like a -1 -1 4 -1 -1 stencil in 2D for example (in practice it’s a bit more complicated) so that I want to compute `A * v` without storing `A` itself in memory (which would be a real waste), only v. The effect of `A` on a given part of `v` would be computed on the fly. I also need to use all my CPU cores as efficiently as possible, make use of SIMD, keep cache locality and minimize memory fetches. Is there a julia package that can help for this kind of problem?

---

<div class="post-metadata">

**Author:** ![simonbyrne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simonbyrne/32/19_2.png) [@simonbyrne](https://discourse.julialang.org/u/simonbyrne)\
**Post date:** [January 15, 2019, 4:58pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/2 "2019-01-15T16:58:46Z")

</div>

If I understand your problem correctly, you might be better off using [`imfilter`](https://juliaimages.org/latest/imagefiltering.html) from the JuliaImages stack, which will avoid allocating a matrix `A`.

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [January 15, 2019, 7:18pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/3 "2019-01-15T19:18:31Z")

</div>

what about a Matrix Free like function if you know how to evaluate it?

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 16, 2019, 7:05am UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/4 "2019-01-16T07:05:42Z")

</div>

> what about a Matrix Free like function if you know how to evaluate it?

Ah, you mean something like `LinearMaps.jl`, yes? It does seem like the perfect solution. However, for the parallelization I guess I would need to take care of that myself when defining the map function. I was hoping to find a specific solution that has been optimised for me already, but I guess that is too much to ask, as the kind of optimization tricks probably depend on `A`.

> If I understand your problem correctly, you might be better off using [`imfilter`](https://juliaimages.org/latest/imagefiltering.html) from the JuliaImages stack, which will avoid allocating a matrix `A` .

This might be closer to what I was looking for, yes! I’ll look into it.

Thanks to both

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [January 16, 2019, 7:17am UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/5 "2019-01-16T07:17:46Z")

</div>

> [@pablosanjose](#):
>
> Ah, you mean something like `LinearMaps.jl` , yes? It does seem like the perfect solution. However, for the parallelization I guess I would need to take care of that myself when defining the map function

Well, you have `DiffEqOperators` for spencils if you dont want to bother writing the forloops on each piece of your distributed vector. And you can use DistributedArrays for managing your vector.

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 16, 2019, 10:08am UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/6 "2019-01-16T10:08:50Z")

</div>

> [@rveltz](#):
>
> DiffEqOperators

Ah, yes! Very nice. Unfortunately my “stencil” is an arbritrary comlicated “hopping” matrix on the lattice discrete. I’m not sure one can add completely arbitrary stencil coefficients with `DiffEqOperators`. I’ll look into it.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [August 19, 2019, 12:05pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/7 "2019-08-19T12:05:55Z")

</div>

> [@pablosanjose](#):
>
> Ah, yes! Very nice. Unfortunately my “stencil” is an arbritrary comlicated “hopping” matrix on the lattice discrete. I’m not sure one can add completely arbitrary stencil coefficients with `DiffEqOperators` . I’ll look into it.

DiffEqOperators handles this case now. It composes operators of different dimensions and does a cache-optimized convolution call. We’ll get the docs updated.

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [August 19, 2019, 12:27pm UTC](https://discourse.julialang.org/t/efficient-multiplication-of-out-of-memory-sparse-matrix-and-an-in-memory-dense-vector/19663/8 "2019-08-19T12:27:55Z")

</div>

Excellent! Looking forward to the docs, thanks!