mathnet/mathnet-symbolics

No effective way to generate large sums

VisualCoder123 opened this issue · 0 comments

Hi!

currently I'm trying to generate a large symbolic expression (over 1 000 000 terms). Unfortunately, performance was not very high so I wrote a benchmark to demonstrate the problem.

The idea of a benchmark is to generate a list of n nonlinear terms (so they wouldn't collapse to one term) and then calculate their sum. I used sin(ix)*cos(iy), i=1..n for nonlinear terms and wrote minimal test code:

open MathNet.Symbolics
open Operators

[<EntryPoint>]
let main argv =
    let x = symbol "x"
    let y = symbol "y"

    let terms n= seq {for i in 1..n -> sin(i*x)*cos(i*y)}

    let sw = new System.Diagnostics.Stopwatch()

    sw.Start()
    let res = terms 10_000 |> Seq.toList |> sum
    sw.Stop()

    printfn "Time %f" sw.Elapsed.TotalMilliseconds
    0

The test evaluated for 53.5 seconds. For a more detailed analysis I excluded list generation from time measurement:

open MathNet.Symbolics
open Operators

[<EntryPoint>]
let main argv =
    let x = symbol "x"
    let y = symbol "y"

    let terms n= seq {for i in 1..n -> sin(i*x)*cos(i*y)}

    let sw = new System.Diagnostics.Stopwatch()
    let evaledTerms = terms 10_000 |> Seq.toList 
    
    sw.Start()
    let res = evaledTerms |> sum
    sw.Stop()

    printfn "Time %f" sw.Elapsed.TotalMilliseconds
    0

Current time is 53.3 seconds. So the problem is in the sum method.

Expressions.fs shows that sum is realized using reduce:

let sum (xs:Expression list) : Expression = if List.isEmpty xs then zero else List.reduce add xs

So to create a sum of n elements it will call add function n times which is not an effective way to generate large sums.

Is there any "unobvious" method in Symbolics to generate this sum from list without using reduce? Using debugger I can see that the final expression contains a list of terms. Can I generate sum by directly passing a list of terms without creating n temporary accumulators?