0 people like it.

# Density of sparse matrix product

A quick exploration of the rather useless question "how does the density of the product of 2 sparse matrices look like?"

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: ``` ``````// Completely useless exploration of the question: // how sparse is the product of 2 sparse matrices? #r "FSharp.PowerPack.dll" let density (M: Matrix) = let elements = M.NumRows * M.NumCols |> (float) let nonZero = M |> Matrix.map (fun e -> if e = 0.0 then 0.0 else 1.0) |> Matrix.sum nonZero / elements let dense = matrix [ [ 42.0; 0.0 ]; [-1.0; 123.0] ] let sparse = matrix [ [ 0.0; 1.0 ]; [ 0.0; 0.0 ] ] printfn "Dense matrix: %f" (density dense) printfn "Sparse matrix: %f" (density sparse) let rng = new System.Random() let create n density = Matrix.create n n 0.0 |> Matrix.map (fun e -> if rng.NextDouble() > density then 0.0 else 1.0) // Run r times the product of 2 matrices // of density d, and size n, and compute // the average density let simulation n d r = Seq.initInfinite (fun index -> let m1 = create n d let m2 = create n d density (m1 * m2)) |> Seq.take r |> Seq.average // Relationship between density and density for density in 0.0 .. 0.05 .. 0.5 do simulation 10 density 1000 |> printfn "Density %f -> Result is %f" density // Relationship between size and density for size in 5 .. 5 .. 50 do simulation size 0.1 1000 |> printfn "Size %i -> Result is %f" size ``````
val density : M:'a -> float

Full name: Script.density
val M : 'a
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val elements : float
val nonZero : float
val dense : obj

Full name: Script.dense
val sparse : obj

Full name: Script.sparse
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val rng : System.Random

Full name: Script.rng
namespace System
Multiple items
type Random =
new : unit -> Random + 1 overload
member Next : unit -> int + 2 overloads
member NextBytes : buffer:byte[] -> unit
member NextDouble : unit -> float

Full name: System.Random

--------------------
System.Random() : unit
System.Random(Seed: int) : unit
val create : n:'a -> density:'b -> 'c

Full name: Script.create
val n : 'a
val density : 'b
System.Random.NextDouble() : float
val simulation : n:'a -> d:'b -> r:int -> float

Full name: Script.simulation
val d : 'b
val r : int
module Seq

from Microsoft.FSharp.Collections
val initInfinite : initializer:(int -> 'T) -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.initInfinite
val index : int
val m1 : int
val m2 : int
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val average : source:seq<'T> -> 'T (requires member ( + ) and member DivideByInt and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.average
val density : float
val size : int