Einsum Expressions in Julia
Home Page: https://bsc-quantic.github.io/EinExprs.jl/
License: Apache License 2.0
Einstein summation notation as symbolic expressions, in a Julia library.
A video of its presentation at JuliaCon 2023 can be seen here:
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "github-actions[bot]")
This issue is used to trigger TagBot; feel free to unsubscribe.
If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.
If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!
As in bsc-quantic/Tenet.jl#139, EinExprs also is missing tests for some parts of its codebase.
EinExpr
Base.copyAbstractTrees.leavesbranches(, i) is missing a testcollapse!flatunique is missing some testsindshistogram(::Vector)Base.sum!/Base.sumBase.stringBase.IteratorEltypeBase.eltypeAbstractTrees interface is missing tests
AbstractTrees.childtypeAbstractTrees.childrentypeAbstractTrees.childstatetypesumtractes is missing coverage in some linesSizedEinExpr
collapse!neighbours
Tenet.neighbors?parsumindsBase.sum!/Base.sumBase.IteratorEltypeBase.eltypeAbstractTrees interface is missing tests
AbstractTrees.childtypeAbstractTrees.childrentypeAbstractTrees.childstatetypefastflopsremovedrank on SizedEinExprBase.selectdim is missing tests for some methodsBase.viewSizeScorerSome optimizers are not ready to work with hyperindices.
Take Tenet's Google Supremacy Experiment as example.
I have noticed that the contract function exhibits unexpected behavior when it attempts to contract EinExpr structures that contain more than two tensors. Upon analysis, it seems that this issue originates from EinExprs calling Tensors.contract with more than two tensors, which leads to an error, as this function is designed to handle only operations with two tensors.
julia> using EinExprs
julia> using Tensors
julia> tensors = [
Tensor(rand(2, 2), (:i, :j)),
Tensor(rand(2, 2), (:j, :k)),
Tensor(rand(2, 2), (:k, :l))]
3-element Vector{Tensor{Float64, 2, Matrix{Float64}}}:
[0.6707986107360668 0.5786583024483742; 0.882255804380894 0.8835566636456639]
[0.4758242461883089 0.7992647660944526; 0.6605684087532678 0.3243026778511521]
[0.23752724861807273 0.5047998353783525; 0.7942985911357734 0.8958411945536674]
julia> expr = EinExpr(tensors)
EinExpr((:i, :l), Any[[0.6707986107360668 0.5786583024483742; 0.882255804380894 0.8835566636456639], [0.4758242461883089 0.7992647660944526; 0.6605684087532678 0.3243026778511521], [0.23752724861807273 0.5047998353783525; 0.7942985911357734 0.8958411945536674]])
julia> contract(expr)
ERROR: MethodError: no method matching contract(::Tensor{Float64, 2, Matrix{Float64}}, ::Tensor{Float64, 2, Matrix{Float64}}, ::Tensor{Float64, 2, Matrix{Float64}}; dims=[:j, :k])
Closest candidates are:
contract(::Tensor, ::Tensor; dims) at ~/.julia/packages/Tensors/4aoee/src/Numerics.jl:10
contract(::Tensor{T, N, A} where {N, A<:AbstractArray{T, N}}, ::Union{AbstractArray{T, 0}, T}) where T at ~/.julia/packages/Tensors/4aoee/src/Numerics.jl:24 got unsupported keyword argument "dims"
contract(::Union{AbstractArray{T, 0}, T}, ::Tensor{T, N, A} where {N, A<:AbstractArray{T, N}}) where T at ~/.julia/packages/Tensors/4aoee/src/Numerics.jl:23 got unsupported keyword argument "dims"
Stacktrace:
[1] contract(expr::EinExpr)
@ EinExprs ~/git/EinExprs.jl/src/EinExpr.jl:190
[2] top-level scope
@ REPL[110]:1Connect with KaHyPar.jl
Currently, optimizers think all the TN graph is connected. Although rare, there are cases in which disconnected components coexist in the same TN.
The optimizers should be able to run on them without any problem (maybe there are some edge-cases, but I wouldn't care about them until someone finds them) but their optimization should run smoother if optimization is run separately on each component, and then finally sum together.
We should have something like TensorOperations.connectedcomponents but implemented as sumtraces; i.e. like a transformation of an EinExpr.
Initially, the retrieved error was:
julia> targetinds = findslices(SizeScorer(), grouppath, size=2^(target_size));
ERROR: MethodError: reducing over an empty collection is not allowed; consider supplying `init` to the reducerWhen replacing this line:
Line 104 in 845cd90
by
original_flops = mapreduce(flops, +, Branches(path; inverse = true); init=zero(BigInt))the obtained set is empty (tested with very small and very big target sizes where the same result was obtained):
julia> targetinds = findslices(SizeScorer(), grouppath, size=2^(target_size))
Set{Symbol}()Implement the slices function, which should look for the optimal n slices of an optimized EinExprs.
CC @lkdvos
In Julia 1.9, Weak Dependencies and Package Dependencies are introduced. Functionality is similar to the one provided by Requires.jl but has the advantage of support for precompilation.
EinExpr can be seen as symbolic expressions that represent linear operations expressible using the Einstein summation notation.
The user can walk through the tree and execute the appropriate methods by identifying the array types with almost no overhead.
But what if we could compile directly these symbolic trees into native code? Could we gain something?
Things to check:
The new implementations of the exhaustive search seem to have some bugs in them, the following works for version 0.5.7, but no longer works on the master branch:
A = EinExpr([:A, :a, :b, :c], Dict(:A => 2, :a => 2, :b => 2, :c => 2))
B = EinExpr([:b, :d, :e, :f], Dict(:b => 2, :d => 2, :e => 2, :f => 2))
C = EinExpr([:a, :e, :g, :C], Dict(:a => 2, :e => 2, :g => 2, :C => 2))
D = EinExpr([:c, :h, :d, :i], Dict(:c => 2, :h => 2, :d => 2, :i => 2))
E = EinExpr([:f, :i, :g, :j], Dict(:f => 2, :i => 2, :g => 2, :j => 2))
F = EinExpr([:B, :h, :k, :l], Dict(:B => 2, :h => 2, :k => 2, :l => 2))
G = EinExpr([:j, :k, :l, :D], Dict(:j => 2, :k => 2, :l => 2, :D => 2))
expr = EinExpr([:A, :B, :C, :D], [A, B, C, D, E, F, G])
config = Exhaustive()
expr_opt = EinExprs.einexpr(config, expr);(v0.5.7)
julia> map(string, branches(expr_opt))
6-element Vector{String}:
"Bhkl,jklD->BhjD"
"chdi,Aabc->hdiAab"
"aegC,figj->aeCfij"
"bdef,aeCfij->bdaCij"
"hdiAab,bdaCij->hACj"
"BhjD,hACj->ABCD"(master)
julia> map(string, branches(expr_opt))
6-element Vector{String}:
"Aabc,bdef->bdef"
"bdef,aegC->egC"
"chdi,figj->igj"
"egC,igj->gj"
"Bhkl,jklD->klD"
"gj,klD->ABCD"The first line is clearly not a valid contraction, as the indices dont add up.
If an hyperindex is present (an index that appears in more than 2 tensors), then optimizers preemptively sum it. This must not happen and it should be sum it in the end if so.
Tests randomly fail.
Example of randomly failing test: https://github.com/bsc-quantic/EinExprs.jl/actions/runs/5096110662/jobs/9161693689
And after relaunch of same workflow: https://github.com/bsc-quantic/EinExprs.jl/actions/runs/5096110662/jobs/9165679386
Incorporate algorithms from https://arxiv.org/abs/2209.12332 to find (in polynomic time) the optimal contraction of any tensor networks with a tree structure.
The contract function is encountering issues when processing EinExpr structures containing more than two unconnected tensors. In a tensor network with interconnected tensors, the optimizer produces a binary tree of contractions executed by Tensors.contract. However, unconnected tensors are overlooked by the optimizer, resulting in more than two tensors being passed to the contract function. Since the contract function currently only supports pairwise contractions, this leads to an error.
To illustrate this issue, consider the following scenario where we are creating an EinExpr with three tensors that are not interconnected:
julia> using EinExprs
julia> using Tensors
julia> tensor_vector = [
Tensor(rand(2, 2), (:i, :j)),
Tensor(rand(2, 2), (:k, :l)),
Tensor(rand(2, 2), (:m, :n))]
3-element Vector{Tensor{Float64, 2, Matrix{Float64}}}: ...
julia> expr = einexpr(Greedy, EinExpr(tensor_vector))
EinExpr((:i, :j, :k, :l, :m, :n), Any[[0.933825756822585 0.08849284100391408; 0.6687884342507102 0.07328036746016686], [0.09743169734991863 0.2589449583415957; 0.9895176422398294 0.3901868918218132], [0.8604998512862905 0.053831101742811915; 0.05133466907086315 0.5293947978388226]])
julia> contract(expr)
ERROR: MethodError: no method matching contract(::Tensor{Float64, 2, Matrix{Float64}}, ::Tensor{Float64, 2, Matrix{Float64}}, ::Tensor{Float64, 2, Matrix{Float64}}; dims=Symbol[])
Closest candidates are:
contract(::Tensor, ::Tensor; dims) at ~/.julia/packages/Tensors/bcSKh/src/Numerics.jl:10
contract(::Tensor, ::TensorNetwork; kwargs...) at ~/git/Tenet.jl/src/TensorNetwork.jl:334
contract(::Tensor{T, N, A} where {N, A<:AbstractArray{T, N}}, ::Union{AbstractArray{T, 0}, T}) where T at ~/.julia/packages/Tensors/bcSKh/src/Numerics.jl:24 got unsupported keyword argument "dims"
...
Stacktrace:
[1] contract(expr::EinExpr)
@ EinExprs ~/.julia/packages/EinExprs/YiZXb/src/EinExpr.jl:183
[2] top-level scope
@ REPL[53]:1Upon running contract(expr), we observe an error as the function does not support contractions involving more than two tensors. A potential resolution may be to enhance the contract function's capability to manage multiple tensors.
Hi there!
I'm been using Tenet the past year during my master's thesis and I stumbled upon a problem when trying to optimize a partial tensor network contraction, instead of a full contraction. The documentation states in einexpr.jl to specify the open indices in the path. But even when specifying the open indices in the einexpr with the outptus = inds(....) - keyword Tenet.contract(network, path=cpath) contracts the whole network?
Example:
output_inds =[Symbol("7"), :v2, Symbol("12"), Symbol("9"), :v3, :v1, Symbol("8"), :v5, Symbol("14"), :v4, Symbol("15")]
cpath = einexpr(transformed_2_mps_network, outputs = output_inds)
mps_network = Tenet.contract(mps_network, path=cpath)
println(typeof(mps_network)) --> return not a tensor network but a single tensor, so contracts all indices and doesn't leave the specified indices open?
See this image for definition of what the indices mean:
I'm trying to plot a random EinExpr but I'm finding a bug on EinExpr v0.2. The problem seems to be related to the ColorBar.
It fails on the plot(path). I want to clarify that this doesn't look like the fault of Makie because plot(tn) works.
]activate --temp
]add Tenet EinExprs NetworkLayout GLMakie
using Tenet
using GLMakie
tn = rand(TensorNetwork, 100, 3)
path = einexpr(tn)
plot(path)(@v1.9) pkg> activate --temp
Activating new project at `/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl`
(jl_qayQMl) pkg> add Tenet EinExprs NetworkLayout GLMakie
Resolving package versions...
Cloning [85d41934-b9cd-44e1-8730-56d86f15f3ec] Tenet from https://github.com/bsc-quantic/Tenet.jl
Installed Tenet ─ v0.2.0
Updating `/private/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl/Project.toml`
⌅ [b1794770] + EinExprs v0.2.0
[e9467ef8] + GLMakie v0.8.7
[46757867] + NetworkLayout v0.4.5
[85d41934] + Tenet v0.2.0
Updating `/private/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl/Manifest.toml`
[621f4979] + AbstractFFTs v1.4.0
[398f06c4] + AbstractLattices v0.2.1
[1520ce14] + AbstractTrees v0.4.4
[79e6a3ab] + Adapt v3.6.2
[27a7e980] + Animations v0.4.1
[ec485272] + ArnoldiMethod v0.2.0
[4fba245c] + ArrayInterface v7.4.11
[a9b6321e] + Atomix v0.1.0
⌅ [67c07d97] + Automa v0.8.3
[13072b0f] + AxisAlgorithms v1.0.1
[39de3d68] + AxisArrays v0.4.7
[ab4f0b2a] + BFloat16s v0.4.2
[a9ab73d0] + BatchedRoutines v0.2.2
[7cffe744] + BetterExp v0.1.0
[e2ed5e7c] + Bijections v0.1.4
[fa961155] + CEnum v0.4.2
[96374032] + CRlibm v1.0.1
[052768ef] + CUDA v4.4.0
[1af6417a] + CUDA_Runtime_Discovery v0.2.2
[49dc2e85] + Calculus v0.5.1
[d360d2e6] + ChainRulesCore v1.16.0
[a2cac450] + ColorBrewer v0.4.0
[35d6a980] + ColorSchemes v3.22.0
[3da002f7] + ColorTypes v0.11.4
⌅ [c3611d14] + ColorVectorSpace v0.9.10
[5ae59095] + Colors v0.12.10
[861a8166] + Combinatorics v1.0.2
[bbf7d656] + CommonSubexpressions v0.3.0
[34da2185] + Compat v4.8.0
[187b0558] + ConstructionBase v1.5.3
[d38c429a] + Contour v0.6.2
[9a962f9c] + DataAPI v1.15.0
[864edb3b] + DataStructures v0.18.14
[e2d170a0] + DataValueInterfaces v1.0.0
[927a84f5] + DelaunayTriangulation v0.7.2
[10b0fc19] + DeltaArrays v0.1.1
[163ba53b] + DiffResults v1.1.0
[b552c78f] + DiffRules v1.15.1
[31c24e10] + Distributions v0.25.98
[ffbed154] + DocStringExtensions v0.9.3
[fa6b7ba4] + DualNumbers v0.6.8
⌅ [b1794770] + EinExprs v0.2.0
[4e289a0a] + EnumX v1.0.4
[90fa49ef] + ErrorfreeArithmetic v0.5.2
[429591f6] + ExactPredicates v2.2.5
[e2ba6199] + ExprTools v0.1.9
[411431e0] + Extents v0.1.1
[c87230d0] + FFMPEG v0.4.1
[7a1cc6ca] + FFTW v1.7.1
[fa42c844] + FastRounding v0.3.1
[5789e2e9] + FileIO v1.16.1
[1a297f60] + FillArrays v1.4.2
[6a86dc24] + FiniteDiff v2.21.1
[53c48c17] + FixedPointNumbers v0.8.4
[59287772] + Formatting v0.4.2
[f6369f11] + ForwardDiff v0.10.35
[b38be410] + FreeType v4.0.0
[663a7486] + FreeTypeAbstraction v0.10.0
[f7f18e0c] + GLFW v3.4.1
[e9467ef8] + GLMakie v0.8.7
[0c68f7d7] + GPUArrays v8.8.1
[46192b85] + GPUArraysCore v0.1.5
[61eb1bfa] + GPUCompiler v0.21.4
[cf35fbd7] + GeoInterface v1.3.1
[5c1252a2] + GeometryBasics v0.4.9
[1ecd5474] + GraphMakie v0.5.5
[a2bd30eb] + Graphics v1.1.2
[86223c79] + Graphs v1.8.0
[3955a311] + GridLayoutBase v0.9.1
[42e2da0e] + Grisu v1.0.2
[34004b35] + HypergeometricFunctions v0.3.21
[2803e5a7] + ImageAxes v0.6.11
⌃ [c817782e] + ImageBase v0.1.5
⌅ [a09fc81d] + ImageCore v0.9.4
[82e4d734] + ImageIO v0.6.7
[bc367c6b] + ImageMetadata v0.9.9
[9b13fd28] + IndirectArrays v1.0.0
[d25df0c9] + Inflate v0.1.3
[18e54dd8] + IntegerMathUtils v0.1.2
[a98d9a8b] + Interpolations v0.14.7
[d1acc4aa] + IntervalArithmetic v0.20.9
[8197267c] + IntervalSets v0.7.4
[92d709cd] + IrrationalConstants v0.2.2
[f1662d9f] + Isoband v0.1.1
[c8e1da08] + IterTools v1.8.0
[82899510] + IteratorInterfaceExtensions v1.0.0
[692b3bcd] + JLLWrappers v1.4.1
[682c06a0] + JSON v0.21.4
[b835a17e] + JpegTurbo v0.1.3
[63c18a36] + KernelAbstractions v0.9.8
[5ab0869b] + KernelDensity v0.6.7
[929cbde3] + LLVM v6.1.0
[b964fa9f] + LaTeXStrings v1.3.0
[8cdb02fc] + LazyModules v0.3.1
[9c8b4983] + LightXML v0.9.0
[d3d80556] + LineSearches v7.2.0
[9b3f67b0] + LinearAlgebraX v0.1.12
[2ab3a3ac] + LogExpFunctions v0.3.24
[1914dd2f] + MacroTools v0.5.10
[ee78f7c6] + Makie v0.19.7
[20f20a25] + MakieCore v0.6.4
[dbb5928d] + MappedArrays v0.4.2
[7eb4fadd] + Match v1.2.0
[0a4f8689] + MathTeXEngine v0.5.6
[c03570c3] + Memoize v0.4.4
[7269a6da] + MeshIO v0.4.10
[e1d29d7a] + Missings v1.1.0
[66fc600b] + ModernGL v1.1.7
[7475f97c] + Mods v1.3.3
[e94cdb99] + MosaicViews v0.3.4
[3b2b4ff1] + Multisets v0.4.4
[d41bc354] + NLSolversBase v7.8.3
[77ba4419] + NaNMath v1.0.2
[f09324ee] + Netpbm v1.1.1
[46757867] + NetworkLayout v0.4.5
[ebe7aa44] + OMEinsum v0.7.4
[6f22d1fd] + OMEinsumContractionOrders v0.8.1
[510215fc] + Observables v0.5.4
[6fe1bfb0] + OffsetArrays v1.12.10
[52e1d378] + OpenEXR v0.3.2
[429524aa] + Optim v1.7.6
[bac558e1] + OrderedCollections v1.6.2
[90014a1f] + PDMats v0.11.17
[f57f5aa1] + PNGFiles v0.4.0
[19eb6ba3] + Packing v0.5.0
[5432bcbf] + PaddedViews v0.5.12
[d96e819e] + Parameters v0.12.3
[69de0a69] + Parsers v2.7.1
[2ae35dd2] + Permutations v0.4.16
[eebad327] + PkgVersion v0.3.2
[995b91a9] + PlotUtils v1.3.5
[647866c9] + PolygonOps v0.1.2
[3a141323] + PolynomialRoots v1.0.0
[f27b6e38] + Polynomials v3.2.13
[85a6dd25] + PositiveFactorizations v0.2.4
[aea7be01] + PrecompileTools v1.1.2
[21216c6a] + Preferences v1.4.0
[27ebfcd6] + Primes v0.5.4
[92933f4c] + ProgressMeter v1.7.2
[4b34888f] + QOI v1.0.0
[1fd47b50] + QuadGK v2.8.2
[74087812] + Random123 v1.6.1
[e6cf234a] + RandomNumbers v1.5.3
[b3c3ace0] + RangeArrays v0.3.2
[c84ed2f1] + Ratios v0.4.5
[3cdcf5f2] + RecipesBase v1.3.4
[189a3867] + Reexport v1.2.2
[05181044] + RelocatableFolders v1.0.0
[ae029012] + Requires v1.3.0
[286e9d63] + RingLists v0.2.7
[79098fc4] + Rmath v0.7.1
[5eaf0fd0] + RoundingEmulator v0.2.1
[fdea26ae] + SIMD v3.4.5
[7b38b023] + ScanByte v0.4.0
[6c6a2e73] + Scratch v1.2.0
[3cc68bcd] + SetRounding v0.2.1
[efcf1570] + Setfield v1.1.1
[65257c39] + ShaderAbstractions v0.3.0
[992d4aef] + Showoff v1.0.3
[73760f76] + SignedDistanceFields v0.4.0
[55797a34] + SimpleGraphs v0.8.4
[ec83eff0] + SimplePartitions v0.3.0
[cc47b68c] + SimplePolynomials v0.2.11
[a6525b86] + SimpleRandom v0.3.1
[699a6c99] + SimpleTraits v0.9.4
[45858cf5] + Sixel v0.1.3
[a2af1166] + SortingAlgorithms v1.1.1
[276daf66] + SpecialFunctions v2.3.0
⌅ [c5dd0088] + StableHashTraits v0.3.1
[cae243ae] + StackViews v0.1.1
[90137ffa] + StaticArrays v1.6.2
[1e83bf80] + StaticArraysCore v1.4.2
[82ae8749] + StatsAPI v1.6.0
[2913bbd2] + StatsBase v0.34.0
[4c63d2b9] + StatsFuns v1.3.0
[09ab397b] + StructArrays v0.6.15
[fd094767] + Suppressor v0.2.4
[3783bdb8] + TableTraits v1.0.1
[bd369af6] + Tables v1.10.1
[85d41934] + Tenet v0.2.0
[62fd8b95] + TensorCore v0.1.1
[a57d67a0] + Tensors v0.1.12
[731e570b] + TiffImages v0.6.4
[a759f4b9] + TimerOutputs v0.5.23
[3bb67fe8] + TranscodingStreams v0.9.13
[410a4b4d] + Tricks v0.1.7
[981d1d27] + TriplotBase v0.1.0
[9d95972d] + TupleTools v1.3.0
[3a884ed6] + UnPack v1.0.2
[1cfade01] + UnicodeFun v0.4.1
[013be700] + UnsafeAtomics v0.2.1
[d80eeb9a] + UnsafeAtomicsLLVM v0.1.3
[0625e100] + ValSplit v0.1.0
[efce3f68] + WoodburyMatrices v0.5.5
[6e34b625] + Bzip2_jll v1.0.8+0
[4e9b3aee] + CRlibm_jll v1.0.1+0
[4ee394cb] + CUDA_Driver_jll v0.5.0+1
[76a88914] + CUDA_Runtime_jll v0.6.0+0
[83423d85] + Cairo_jll v1.16.1+1
[5ae413db] + EarCut_jll v2.2.4+0
[2e619515] + Expat_jll v2.5.0+0
[b22a6f82] + FFMPEG_jll v4.4.2+2
[f5851436] + FFTW_jll v3.3.10+0
[a3f928ae] + Fontconfig_jll v2.13.93+0
⌅ [d7e528f0] + FreeType2_jll v2.10.4+0
[559328eb] + FriBidi_jll v1.0.10+0
[0656b61e] + GLFW_jll v3.3.8+0
[78b55507] + Gettext_jll v0.21.0+0
[7746bdde] + Glib_jll v2.74.0+2
[3b182d85] + Graphite2_jll v1.3.14+0
[2e76f6c2] + HarfBuzz_jll v2.8.1+1
[905a6f67] + Imath_jll v3.1.7+0
[1d5cc7b8] + IntelOpenMP_jll v2023.1.0+0
[aacddb02] + JpegTurbo_jll v2.1.91+0
[c1c5ebd0] + LAME_jll v3.100.1+0
[dad2f222] + LLVMExtra_jll v0.0.23+0
[1d63c593] + LLVMOpenMP_jll v15.0.4+0
[dd4b983a] + LZO_jll v2.10.1+0
⌅ [e9f186c6] + Libffi_jll v3.2.2+1
[d4300ac3] + Libgcrypt_jll v1.8.7+0
[7e76a0d4] + Libglvnd_jll v1.6.0+0
[7add5ba3] + Libgpg_error_jll v1.42.0+0
[94ce4f54] + Libiconv_jll v1.16.1+2
[4b2f31a3] + Libmount_jll v2.35.0+0
[38a345b3] + Libuuid_jll v2.36.0+0
[856f044c] + MKL_jll v2023.1.0+0
[e7412a2a] + Ogg_jll v1.3.5+1
[18a262bb] + OpenEXR_jll v3.1.4+0
⌅ [458c3c95] + OpenSSL_jll v1.1.21+0
[efe28fd5] + OpenSpecFun_jll v0.5.5+0
[91d4177d] + Opus_jll v1.3.2+0
[30392449] + Pixman_jll v0.42.2+0
[f50d1b31] + Rmath_jll v0.4.0+0
[02c8fc9c] + XML2_jll v2.10.3+0
[aed1982a] + XSLT_jll v1.1.34+0
[4f6342f7] + Xorg_libX11_jll v1.8.6+0
[0c0b7dd1] + Xorg_libXau_jll v1.0.11+0
[935fb764] + Xorg_libXcursor_jll v1.2.0+4
[a3789734] + Xorg_libXdmcp_jll v1.1.4+0
[1082639a] + Xorg_libXext_jll v1.3.4+4
[d091e8ba] + Xorg_libXfixes_jll v5.0.3+4
[a51aa0fd] + Xorg_libXi_jll v1.7.10+4
[d1454406] + Xorg_libXinerama_jll v1.1.4+4
[ec84b674] + Xorg_libXrandr_jll v1.5.2+4
[ea2f1a96] + Xorg_libXrender_jll v0.9.10+4
[14d82f49] + Xorg_libpthread_stubs_jll v0.1.1+0
[c7cfdc94] + Xorg_libxcb_jll v1.15.0+0
[c5fb5394] + Xorg_xtrans_jll v1.5.0+0
[9a68df92] + isoband_jll v0.2.3+0
[a4ae2306] + libaom_jll v3.4.0+0
[0ac62f75] + libass_jll v0.15.1+0
[f638f0a6] + libfdk_aac_jll v2.0.2+0
[b53b4c65] + libpng_jll v1.6.38+0
[075b6546] + libsixel_jll v1.10.3+0
[f27f6e37] + libvorbis_jll v1.3.7+1
[1270edf5] + x264_jll v2021.5.5+0
[dfaa095f] + x265_jll v3.5.0+0
[0dad84c5] + ArgTools v1.1.1
[56f22d72] + Artifacts
[2a0f44e3] + Base64
[8bf52ea8] + CRC32c
[ade2ca70] + Dates
[8ba89e20] + Distributed
[f43a241f] + Downloads v1.6.0
[7b1f6079] + FileWatching
[9fa8497b] + Future
[b77e0a4c] + InteractiveUtils
[4af54fe1] + LazyArtifacts
[b27032c2] + LibCURL v0.6.3
[76f85450] + LibGit2
[8f399da3] + Libdl
[37e2e46d] + LinearAlgebra
[56ddb016] + Logging
[d6f4376e] + Markdown
[a63ad114] + Mmap
[ca575930] + NetworkOptions v1.2.0
[44cfe95a] + Pkg v1.9.2
[de0858da] + Printf
[3fa0cd96] + REPL
[9a3f8284] + Random
[ea8e919c] + SHA v0.7.0
[9e88b42a] + Serialization
[1a1011a3] + SharedArrays
[6462fe0b] + Sockets
[2f01184e] + SparseArrays
[10745b16] + Statistics v1.9.0
[4607b0f0] + SuiteSparse
[fa267f1f] + TOML v1.0.3
[a4e569a6] + Tar v1.10.0
[8dfed614] + Test
[cf7118a7] + UUIDs
[4ec0a83e] + Unicode
[e66e0078] + CompilerSupportLibraries_jll v1.0.5+0
[deac9b47] + LibCURL_jll v7.84.0+0
[29816b5a] + LibSSH2_jll v1.10.2+0
[c8ffd9c3] + MbedTLS_jll v2.28.2+0
[14a3606d] + MozillaCACerts_jll v2022.10.11
[4536629a] + OpenBLAS_jll v0.3.21+4
[05823500] + OpenLibm_jll v0.8.1+0
[efcefdf7] + PCRE2_jll v10.42.0+0
[bea87d4a] + SuiteSparse_jll v5.10.1+6
[83775a58] + Zlib_jll v1.2.13+0
[8e850b90] + libblastrampoline_jll v5.8.0+0
[8e850ede] + nghttp2_jll v1.48.0+0
[3f19e933] + p7zip_jll v17.4.0+0
Info Packages marked with ⌃ and ⌅ have new versions available, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m`
Precompiling project...
5 dependencies successfully precompiled in 12 seconds. 284 already precompiled.
julia> using Tenet
[ Info: Precompiling Tenet [85d41934-b9cd-44e1-8730-56d86f15f3ec]
(jl_qayQMl) pkg> up
Updating registry at `~/.julia/registries/Quantic`
Updating git-repo `https://github.com/bsc-quantic/Registry`
Updating registry at `~/.julia/registries/General.toml`
No Changes to `/private/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl/Project.toml`
No Changes to `/private/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl/Manifest.toml`
Precompiling project...
2 dependencies successfully precompiled in 17 seconds. 287 already precompiled.
1 dependency had warnings during precompilation:
┌ EinExprsMakieExt [b477e11c-43e4-5160-8a95-c955a1659e49]
│ ┌ Warning: Module EinExprs with build ID fafbfcfd-cee3-63cf-0003-d3b298ba2f5a is missing from the cache.
│ │ This may mean EinExprs [b1794770-133b-4de1-afb4-526377e9f4c5] does not support precompilation but is imported by a module that does.
│ └ @ Base loading.jl:1793
│ ┌ Error: Error during loading of extension EinExprsChainRulesCoreExt of EinExprs, use `Base.retry_load_extensions()` to retry.
│ │ exception =
│ │ 1-element ExceptionStack:
│ │ Declaring __precompile__(false) is not allowed in files that are being precompiled.
│ │ Stacktrace:
│ │ [1] _require(pkg::Base.PkgId, env::Nothing)
│ │ @ Base ./loading.jl:1825
│ │ [2] _require_prelocked(uuidkey::Base.PkgId, env::Nothing)
│ │ @ Base ./loading.jl:1660
│ │ [3] _require_prelocked(uuidkey::Base.PkgId)
│ │ @ Base ./loading.jl:1658
│ │ [4] run_extension_callbacks(extid::Base.ExtensionId)
│ │ @ Base ./loading.jl:1255
│ │ [5] run_extension_callbacks(pkgid::Base.PkgId)
│ │ @ Base ./loading.jl:1290
│ │ [6] run_package_callbacks(modkey::Base.PkgId)
│ │ @ Base ./loading.jl:1124
│ │ [7] _require_prelocked(uuidkey::Base.PkgId, env::String)
│ │ @ Base ./loading.jl:1667
│ │ [8] macro expansion
│ │ @ ./loading.jl:1648 [inlined]
│ │ [9] macro expansion
│ │ @ ./lock.jl:267 [inlined]
│ │ [10] require(into::Module, mod::Symbol)
│ │ @ Base ./loading.jl:1611
│ │ [11] top-level scope
│ │ @ ~/.julia/packages/EinExprs/KrAtE/ext/EinExprsMakieExt.jl:4
│ │ [12] include
│ │ @ ./Base.jl:457 [inlined]
│ │ [13] include_package_for_output(pkg::Base.PkgId, input::String, depot_path::Vector{String}, dl_load_path::Vector{String}, load_path::Vector{String}, concrete_deps::Vector{Pair{Base.PkgId, UInt128}}, source::Nothing)
│ │ @ Base ./loading.jl:2049
│ │ [14] top-level scope
│ │ @ stdin:3
│ │ [15] eval
│ │ @ ./boot.jl:370 [inlined]
│ │ [16] include_string(mapexpr::typeof(identity), mod::Module, code::String, filename::String)
│ │ @ Base ./loading.jl:1903
│ │ [17] include_string
│ │ @ ./loading.jl:1913 [inlined]
│ │ [18] exec_options(opts::Base.JLOptions)
│ │ @ Base ./client.jl:305
│ │ [19] _start()
│ │ @ Base ./client.jl:522
│ └ @ Base loading.jl:1261
└
julia> Base.retry_load_extensions()
julia> tn = rand(TensorNetwork, 100, 3);
julia> path = einexpr(tn);
julia> using GLMakie
[ Info: Precompiling GLMakie [e9467ef8-e4e7-5192-8a1a-b1aee30e663a]
[ Info: Precompiling EinExprsMakieExt [b477e11c-43e4-5160-8a95-c955a1659e49]
┌ Warning: Module EinExprs with build ID fafbfcfd-9198-7cc2-0003-d3af22976edf is missing from the cache.
│ This may mean EinExprs [b1794770-133b-4de1-afb4-526377e9f4c5] does not support precompilation but is imported by a module that does.
└ @ Base loading.jl:1793
[ Info: Skipping precompilation since __precompile__(false). Importing EinExprsMakieExt [b477e11c-43e4-5160-8a95-c955a1659e49].
[ Info: Precompiling Graphs [86223c79-3864-5bf0-83f7-82e725a168b6]
[ Info: Precompiling GraphMakie [1ecd5474-83a3-4783-bb4f-06765db800d2]
[ Info: Precompiling TenetMakieExt [69371dbe-9d29-560b-9f16-9e308cd205a7]
┌ Warning: Module Tenet with build ID fafbfcfd-24f2-a248-0003-d3af0b8882ec is missing from the cache.
│ This may mean Tenet [85d41934-b9cd-44e1-8730-56d86f15f3ec] does not support precompilation but is imported by a module that does.
└ @ Base loading.jl:1793
[ Info: Skipping precompilation since __precompile__(false). Importing TenetMakieExt [69371dbe-9d29-560b-9f16-9e308cd205a7].
julia> plot(path)
ERROR: KeyError: key :colorscale not found
Stacktrace:
[1] getindex(h::Dict{Symbol, Observable}, key::Symbol)
@ Base ./dict.jl:484
[2] getindex
@ ~/.julia/packages/MakieCore/bttjb/src/attributes.jl:89 [inlined]
[3] getindex(x::Combined{GraphMakie.edgeplot, Tuple{Vector{GraphMakie.Line{Point{2, Float32}}}}}, key::Symbol)
@ MakieCore ~/.julia/packages/MakieCore/bttjb/src/attributes.jl:185
[4] getproperty
@ ~/.julia/packages/MakieCore/bttjb/src/attributes.jl:76 [inlined]
[5] Colorbar(fig_or_scene::GridSubposition, plot::Combined{GraphMakie.edgeplot, Tuple{Vector{GraphMakie.Line{Point{2, Float32}}}}}; kwargs::Base.Pairs{Symbol, Any, NTuple{4, Symbol}, NamedTuple{(:label, :flipaxis, :flip_vertical_label, :labelsize), Tuple{LaTeXStrings.LaTeXString, Bool, Bool, Int64}}})
@ Makie ~/.julia/packages/Makie/uAmck/src/makielayout/blocks/colorbar.jl:36
[6] plot!(f::GridPosition, path::EinExprs.EinExpr; kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
@ EinExprsMakieExt ~/.julia/packages/EinExprs/KrAtE/ext/EinExprsMakieExt.jl:43
[7] plot!
@ ~/.julia/packages/EinExprs/KrAtE/ext/EinExprsMakieExt.jl:26 [inlined]
[8] #plot#1
@ ~/.julia/packages/EinExprs/KrAtE/ext/EinExprsMakieExt.jl:22 [inlined]
[9] plot(path::EinExprs.EinExpr)
@ EinExprsMakieExt ~/.julia/packages/EinExprs/KrAtE/ext/EinExprsMakieExt.jl:20
[10] top-level scope
@ REPL[10]:1(jl_qayQMl) pkg> st
Status `/private/var/folders/wb/4jh3glzx5ng9nqh7f2s83vrc0000gn/T/jl_qayQMl/Project.toml`
⌅ [b1794770] EinExprs v0.2.0
[e9467ef8] GLMakie v0.8.7
[46757867] NetworkLayout v0.4.5
[85d41934] Tenet v0.2.0
Info Packages marked with ⌅ have new versions available but compatibility constraints restrict them from upgrading. To see why use `status --outdated`
I'm not sure why there is this mismatch but I've found the number of FLOPs reported by EinExprs is approximately half of what opt_einsum reports.
I believe that it might be because we are only counting floating-point multiplications, and not sums.
If that is the case, should we really consider counting sums? Current implementations use fmad instructions (i.e. Fused Multiply And Add) which fuse multiplication and addition in only one instruction.
Currently, there is a speed bottleneck on allocating many small sized objects when running an optimizer (specially, the Exhaustive). If we use some pool or stack allocator, the overhead would be amortized and these allocations would be free to perform.
ijik->jk: Partial Trace
ii->: Traceikjl,mnkl->ijmn: Tensor Contraction
ik,kj->jk: Matrix Multiplicationijkl->ilkj: Tensor Index Permutation
ij->ji: Matrix transpositionij,ij->ij: Hadamard (element-wise) productI was running some benchmarks on random networks, and ran into the following issue:
ex_problem = sum([EinExpr([1, 1]), EinExpr([2, 3]), EinExpr([3, 4])])
sized_ex_problem = SizedEinExpr(ex_problem, Dict(i => 2 for i in 1:4))
einexpr(Exhaustive(; outer=true), sized_ex_problem) # works
einexpr(Exhaustive(; outer=false), sized_ex_problem) # hangsThe problem here being that even though I would want the algorithm to not consider outer products in general, the network does consist of actual disconnected components, and needs an outer product to connect these. In particular, this does not increase the complexity of the algorithm to
In any case, I feel like there should probably be at least some error being thrown, instead of just being stuck in an infinite loop somewhere.
The function findslices crashes for some circuits for the FlopsScorer scorer. The error is due to a negative value in the log computed in this line.
using QuacIO
using Tenet
using EinExprs
_sites = [5, 6, 14, 15, 16, 17, 24, 25, 26, 27, 28, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 61, 62, 63, 64, 65, 66, 67, 72, 73, 74, 75, 76, 83, 84, 85, 94];
# load circuit and convert to `TensorNetwork`
circuit = QuacIO.parse(joinpath(@__DIR__, "sycamore_53_8_0.txt"), format = QuacIO.Qflex(), sites = _sites);
tn = TensorNetwork(circuit)
function find_optimal_path(tn)
_minflops = Inf # Initialize to a large number
_path = nothing
path_time = @elapsed begin
for _ in 1:100
returnable = einexpr(tn, optimizer = Greedy)
current_flops = flops(returnable)
# If current result is better, update our current best values
if current_flops < _minflops
_minflops = current_flops
_path = returnable
end
end
end
return _path, _minflops, path_time
end
_path, minflops, path_time = find_optimal_path(tn)
# Similarly for the contraction process:
cuttings = findslices(FlopsScorer(), _path, slices=10)
contraction_time = @elapsed begin
result = zero(eltype(_path)) # Initialize to zero of the path's element type
for proj_inds in collect(product(cuttings...))
slice = @view _path[proj_inds...]
println("slice: $slice, flops: $(flops(slice))")
println("result: $result")
result += contract(slice)
endWe get the error:
ERROR: DomainError with -2.13782433518385e14:
log will only return a complex result if called with a complex argument. Try log(Complex(x)).
Stacktrace:
[1] throw_complex_domainerror(f::Symbol, x::Float64)
@ Base.Math ./math.jl:33
[2] _log(x::Float64, base::Val{:ℯ}, func::Symbol)
@ Base.Math ./special/log.jl:301
[3] log(x::Float64)
@ Base.Math ./special/log.jl:267
[4] (::FlopsScorer)(path::EinExpr, index::Symbol)
@ EinExprs ~/.julia/packages/EinExprs/1f4Lk/src/Slicing.jl:128
[5] (::EinExprs.var"#32#34"{Float64, FlopsScorer})(index::Symbol)
@ EinExprs ~/.julia/packages/EinExprs/1f4Lk/src/Slicing.jl:85
[6] #310
@ ./reduce.jl:1015 [inlined]
[7] MappingRF
@ ./reduce.jl:95 [inlined]
[8] _foldl_impl(op::Base.MappingRF{Base.var"#310#311"{EinExprs.var"#32#34"{Float64, FlopsScorer}}, Base.BottomRF{typeof(Base._rf_findmax)}}, init::Base._InitialValue, itr::Set{Symbol})
@ Base ./reduce.jl:62
[9] foldl_impl
@ ./reduce.jl:48 [inlined]
[10] mapfoldl_impl
@ ./reduce.jl:44 [inlined]
[11] #mapfoldl#288
@ ./reduce.jl:170 [inlined]
[12] mapfoldl
@ ./reduce.jl:170 [inlined]
[13] argmax(f::EinExprs.var"#32#34"{Float64, FlopsScorer}, domain::Set{Symbol})
@ Base ./reduce.jl:1015
[14] findslices(scorer::FlopsScorer, path::EinExpr; size::Nothing, overhead::Nothing, slices::Int64, temperature::Float64, skip::NTuple{106, Symbol})
@ EinExprs ~/.julia/packages/EinExprs/1f4Lk/src/Slicing.jl:84
[15] top-level scopeSome potential users (CC @lkdvos @Jutho) want to use EinExprs in their packages, but currently it would be impossible to register that 3rd party package, which uses EinExprs, in the "General" registry due to EinExprs only being available in our registry.
Packages in our registry are able to use packages from the "General" registry, but NOT the other way around.
I think EinExprs has stabilized enough to be considered to move to the "General" registry. We don't expect large refactors of its API or codebase (apart of #36), even if it hasn't reached yet v1.0. EinExprs is no longer an experiment and I want to consider it ready for production.
There are no dependencies in There is EinExprs v0.5 attaching it to our registry, but some past versions did. I guess that we can only move EinExprs from v0.5 upwards, but we have to check that this is the standard proceeding.ImmutableArrays dependency in v0.5 so we can only transfer it from v0.6.
In the context of specific tensor network algorithms, often the sizes of some of the tensors are not fixed, and typically one of the sizes is used as a parameter to tune the accuracy/expressiveness of some of the tensor network ansatzes. (For example, the bonddimension of a matrix product state).
It would be cool to be able to specify a contraction cost that is a symbolic polynomial in some variable, and to determine the optimal order in the limit where this specific size dominates. This effectively means that the metric of optimizing is to select the order that minimizes the exponent of that symbolic variable, and then selects the option with the smallest prefactor.
As a concrete example of what I mean, this exists in TensorOperations.jl, see for example the section on @tensoropt.
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.