Fastest way to convert two associations into a sparse matrix

Question

I have two association $N$ and $C$

$N$ has this form : $N=<|x_1\rightarrow \{x_{1,1},...x_{1,p_1}\},x_2\rightarrow \{x_{2,1},...x_{2,p_2}\}...,x_D\rightarrow \{x_{D1},...x_{Dp_D}\} |>$

$C$ has this form : $C=<|x_1\rightarrow \{c_{1,1},...c_{1,p_1}\},x_2\rightarrow \{c_{2,1},...c_{2,p_2}\}...,x_D\rightarrow \{c_{D1},...c_{Dp_D}\} |>$

The $x_i$ represent basis vectors, the $c_i$ are couplings between these vectors (or matrix elements if you wish). $N$ therefore represents the states to which a given basis vector $x_i$ is coupled, and $C$ the couplings between the $x_i$.

Question: Is there a fast way to convert these two associations into the corresponding sparse matrix $M$ ?

EDIT: The $\{x_i,x_{i,n}\}$ element of the matrix $M$ is given by $c_{i,n}$ that is the real number in Association $C$ that is called by N[[Key[[x_i]]]][[n]]. Basically, in matrix $M$ entry {x_i ,N [[key[[x_i]] ]] [[n]] } is given by C [[key[[x_i]] ]] [[n]]

Additional info: $D\sim 6 000 000$ in reality so I will not be posting the associations! Typically one state is coupled to about 80 other states or so (i.e. $p_i \sim 80$). The $x_i$ are integers with 13 to 15 digits. The $c_i$ are real numbers.

My goal is to compare the speed of carrying calculation of the type $M^k X$, where $X$ is an initial vector, using the sparse matrix $M$ if I can create it or the associations $N,C$ directly.

Below a miniversion of $N$ and $C$ (as it is a truncated version, you might be better off not using it, some of the neighbours states in $N$ are not in $C$, but just to give you an idea. In particular, $N$ and $C$ are not sorted. FOR EXAMPLE the {15532192698680,17313748593344} entry of matrix $M$ is -1.35158, i.e. the first number in the list of couplings of state 15532192698680 in $C$ , is the coupling to the first neighbour of state 15532192698680 in $N$) :

$N$

 <|15532192698680 -> {17313748593344, 17323537361996, 17186494600868, 
   13877890796492, 15659446691156, 15669235459808, 13750636804016, 
   15542734449536, 15542792371244, 15541981467332, 15404938706204, 
   15395149937552, 13740848035364, 15522403930028, 15532945680884, 
   15533003602592, 15521650947824, 15532255075904, 15532255418636, 
   15532250620388, 15531439716476, 15531381794768, 15521593026116, 
   15532134776972, 15532197154196, 15532197496928}, 
 17313748593344 -> {15659446691156, 17441002585820, 17450791354472, 
   15532192698680, 17324290344200, 17324348265908, 17323537361996, 
   17186494600868, 17176705832216, 15522403930028, 17303959824692, 
   17314501575548, 17314559497256, 17303206842488, 17313810970568, 
   17313811313300, 17313806515052, 17312995611140, 17312937689432, 
   17303148920780, 17313690671636, 17313753048860, 17313753391592, 
   17313686216120, 17313748962440, 17313748964468, 17313748936076, 
   17313744137828, 17313743795096, 17313685873388, 17313748250612, 
   17313748619708, 17313748621736, 17313748224248, 17313748595528, 
   17313748595540, 17313748595372, 17313748566980, 17313748564952, 
   17313748222220, 17313748591316, 17313748593500, 17313748593512, 
   17313748591160, 17313748593356, 17313748593188, 17313748593176, 
   17313748591148, 17313748593332}, 
 17323537361996 -> {15669235459808, 17450791354472, 17460580123124, 
   15541981467332, 17334079112852, 17334137034560, 17333326130648, 
   17196283369520, 17186494600868, 15532192698680, 17313748593344, 
   17324290344200, 17324348265908, 17312995611140, 17323599739220, 
   17323600081952, 17323595283704, 17322784379792, 17322726458084, 
   17312937689432, 17323479440288, 17323541817512, 17323542160244, 
   17323474984772, 17323537731092, 17323537733120, 17323537704728, 
   17323532906480, 17323532563748, 17323474642040, 17323537019264, 
   17323537388360, 17323537390388, 17323536992900, 17323537364180, 
   17323537364192, 17323537364024, 17323537335632, 17323537333604, 
   17323536990872, 17323537359968, 17323537362152, 17323537362164, 
   17323537359812, 17323537362008, 17323537361840, 17323537361828, 
   17323537359800, 17323537361984}, 
 17186494600868 -> {15532192698680, 17313748593344, 17323537361996, 
   15404938706204, 17197036351724, 17197094273432, 17196283369520, 
   17059240608392, 17049451839740, 15395149937552, 17176705832216, 
   17187247583072, 17187305504780, 17175952850012, 17186556978092, 
   17186557320824, 17186552522576, 17185741618664, 17185683696956, 
   17175894928304, 17186436679160, 17186499056384, 17186499399116, 
   17186432223644, 17186494969964, 17186494971992, 17186494943600, 
   17186490145352, 17186489802620, 17186431880912, 17186494258136, 
   17186494627232, 17186494629260, 17186494231772, 17186494603052, 
   17186494603064, 17186494602896, 17186494574504, 17186494572476, 
   17186494229744, 17186494598840, 17186494601024, 17186494601036, 
   17186494598684, 17186494600880, 17186494600712, 17186494600700, 
   17186494598672, 17186494600856}, 
 13877890796492 -> {15659446691156, 15669235459808, 15532192698680, 
   12096334901828, 13888432547348, 13888490469056, 13887679565144, 
   13750636804016, 13740848035364, 12086546133176, 13868102027840, 
   13878643778696, 13878701700404, 13867349045636, 13877953173716, 
   13877953516448, 13877948718200, 13877137814288, 13877079892580, 
   13867291123928, 13877832874784, 13877895252008, 13877895594740, 
   13877828419268, 13877891165588, 13877891167616, 13877891139224, 
   13877886340976, 13877885998244, 13877828076536, 13877890453760, 
   13877890822856, 13877890824884, 13877890427396, 13877890798676, 
   13877890798688, 13877890798520, 13877890770128, 13877890768100, 
   13877890425368, 13877890794464, 13877890796648, 13877890796660, 
   13877890794308, 13877890796504, 13877890796336, 13877890796324, 
   13877890794296, 13877890796480}, 
 15659446691156 -> {17441002585820, 17450791354472, 17313748593344, 
   13877890796492, 15669988442012, 15670046363720, 15669235459808, 
   15532192698680, 15522403930028, 13868102027840, 15649657922504, 
   15660199673360, 15660257595068, 15648904940300, 15659509068380, 
   15659509411112, 15659504612864, 15658693708952, 15658635787244, 
   15648847018592, 15659388769448, 15659451146672, 15659451489404, 
   15659384313932, 15659447060252, 15659447062280, 15659447033888, 
   15659442235640, 15659441892908, 15659383971200, 15659446348424, 
   15659446717520, 15659446719548, 15659446322060, 15659446693340, 
   15659446693352, 15659446693184, 15659446664792, 15659446662764, 
   15659446320032, 15659446689128, 15659446691312, 15659446691324, 
   15659446688972, 15659446691168, 15659446691000, 15659446690988, 
   15659446688960, 15659446691144}, 
 15669235459808 -> {17450791354472, 17460580123124, 17323537361996, 
   13887679565144, 15679777210664, 15679835132372, 15679024228460, 
   15541981467332, 15532192698680, 13877890796492, 15659446691156, 
   15669988442012, 15670046363720, 15658693708952, 15669297837032, 
   15669298179764, 15669293381516, 15668482477604, 15668424555896, 
   15658635787244, 15669177538100, 15669239915324, 15669240258056, 
   15669173082584, 15669235828904, 15669235830932, 15669235802540, 
   15669231004292, 15669230661560, 15669172739852, 15669235117076, 
   15669235486172, 15669235488200, 15669235090712, 15669235461992, 
   15669235462004, 15669235461836, 15669235433444, 15669235431416, 
   15669235088684, 15669235457780, 15669235459964, 15669235459976, 
   15669235457624, 15669235459820, 15669235459652, 15669235459640, 
   15669235457612, 15669235459796}, 
 13750636804016 -> {15532192698680, 15541981467332, 15404938706204, 
   12096334901828, 13877890796492, 13887679565144, 13613594042888, 
   11959292140700, 13740848035364, 13751389786220, 13751447707928, 
   13740095053160, 13750699181240, 13750699523972, 13750694725724, 
   13749883821812, 13749825900104, 13740037131452, 13750578882308, 
   13750641259532, 13750641602264, 13750574426792, 13750637173112, 
   13750637175140, 13750637146748, 13750632348500, 13750632005768, 
   13750574084060, 13750636461284, 13750636830380, 13750636832408, 
   13750636434920, 13750636806200, 13750636806212, 13750636806044, 
   13750636777652, 13750636775624, 13750636432892, 13750636801988, 
   13750636804172, 13750636804184, 13750636801832, 13750636804028, 
   13750636803860, 13750636803848, 13750636801820, 13750636804004}, 
 15542734449536 -> {17324290344200, 17334079112852, 17197036351724, 
   13888432547348, 15669988442012, 15679777210664, 15405691688408, 
   13751389786220, 15532945680884, 15543487431740, 15543545353448, 
   15532192698680, 15542796826760, 15542797169492, 15542792371244, 
   15541981467332, 15541923545624, 15532134776972, 15542676527828, 
   15542738905052, 15542739247784, 15542672072312, 15542734818632, 
   15542734820660, 15542734792268, 15542729994020, 15542729651288, 
   15542671729580, 15542734106804, 15542734475900, 15542734477928, 
   15542734080440, 15542734451720, 15542734451732, 15542734451564, 
   15542734423172, 15542734421144, 15542734078412, 15542734447508, 
   15542734449692, 15542734449704, 15542734447352, 15542734449548, 
   15542734449380, 15542734449368, 15542734447340, 15542734449524}, 
 15542792371244 -> {17324348265908, 17334137034560, 17197094273432, 
   13888490469056, 15670046363720, 15679835132372, 15405749610116, 
   13751447707928, 15533003602592, 15543545353448, 15543603275156, 
   15532250620388, 15542854748468, 15542855091200, 15542850292952, 
   15542039389040, 15541981467332, 15532192698680, 15542734449536, 
   15542796826760, 15542797169492, 15542729994020, 15542792740340, 
   15542792742368, 15542792713976, 15542787915728, 15542787572996, 
   15542729651288, 15542792028512, 15542792397608, 15542792399636, 
   15542792002148, 15542792373428, 15542792373440, 15542792373272, 
   15542792344880, 15542792342852, 15542792000120, 15542792369216, 
   15542792371400, 15542792371412, 15542792369060, 15542792371256, 
   15542792371088, 15542792371076, 15542792369048, 15542792371232}|>

$C$

<|15532192698680 -> {-1.35158, -0.275725, 3.28807, 3.28807, 
   0.960378, -1.35158, -1.35158, -2.34101, -0.47757, 3.28807, 
   0.960378, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -2.58808, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.527974, 10.9053, 3.18522, -4.48269}, 
 17313748593344 -> {2.54693, 
   1.05204, -1.35158, -1.35158, -3.02223, -0.61654, 4.24488, 
   1.23984, -1.35158, -0.213576, 3.6019, 
   1.66342, -2.34101, -2.8351, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.578366, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 17323537361996 -> {2.54693, 
   0.960378, -1.48058, -1.04693, -2.34101, -0.47757, 3.6019, 
   0.960378, -1.74488, -0.275725, 4.24488, 
   2.14747, -3.02223, -2.58808, -4.48269, -0.914477, 10.9053, 
   2.01451, -2.8351, -0.527974, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 17186494600868 -> {3.28807, 
   1.23984, -1.74488, -1.04693, -2.34101, -0.47757, 3.28807, 
   1.05204, -1.48058, -0.213576, 3.28807, 
   1.66342, -2.34101, -2.58808, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 13877890796492 -> {-1.74488, -0.35596, 
   3.28807, -1.48058, -2.34101, -0.47757, 3.28807, 
   0.743906, -1.04693, -0.302042, 3.28807, 
   1.66342, -2.34101, -2.58808, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 15659446691156 -> {-1.48058, -0.275725, 
   2.54693, -1.74488, -3.02223, -0.61654, 4.24488, 
   0.960378, -1.04693, -0.275725, 3.6019, 
   1.66342, -2.34101, -2.8351, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.578366, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 15669235459808 -> {-1.35158, -0.302042, 
   2.54693, -1.35158, -2.34101, -0.47757, 3.6019, 
   0.743906, -1.35158, -0.35596, 4.24488, 
   2.14747, -3.02223, -2.58808, -4.48269, -0.914477, 10.9053, 
   2.01451, -2.8351, -0.527974, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 13750636804016 -> {-1.35158, -0.35596, 4.24488, 3.6019, 
   0.743906, -1.35158, -1.35158, -0.302042, 2.54693, 
   1.66342, -2.34101, -2.00472, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -0.408967, 10.9053, 
   3.18522, -4.48269, -4.48269, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 15542734449536 -> {-1.04693, -0.275725, 3.28807, 3.28807, 
   0.743906, -1.35158, -1.35158, -0.275725, 2.54693, 
   1.82219, -2.34101, 0., -5.23465, -1.06788, 12.7346, 
   0., -2.58808, -0.408967, 11.9462, 
   3.18522, -4.48269, -4.91054, -2.58808, -0.527974, 10.9053, 
   3.18522, -4.48269, -1.00176, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}, 
 15542792371244 -> {-1.04693, -0.275725, 3.28807, 3.28807, 
   0.743906, -1.35158, -1.35158, -0.275725, 2.54693, 
   1.66342, -2.56444, -2.00472, -4.48269, -0.914477, 11.9462, 1.83898,
    0., 0., 12.7346, 3.71953, -5.23465, -4.48269, -2.58808, -0.527974,
    10.9053, 3.48923, -4.91054, -0.914477, 10.9053, 
   1.83898, -2.58808, -2.34101, -1.35158, -0.275725, 3.28807, 
   1.66342, -2.34101, -0.47757, 3.28807, 0.960378, -1.35158, -1.35158,
    3.28807, 0.960378, -1.35158, -0.275725, 3.28807}|>

It is completely unclear to me from your question how the transformation ought to be done mathematically. In other words, if I want to calculate the generic element {i, j} of the sparse matrix, what formula do I need to apply and what is the relationship with your numbers? If it's easier, what about element {1, 1}? — MarcoB, Commented Mar 17, 2021 at 14:36
I'm going to edit my question ! The $\{x_i,x_{i,n}\}$ element of the matrix $M$ is given by $c_{i,n}$, that is the real number in Association $C$ that is called by N[[Key[[x_i]]]][[n]]., does this answer your question ? @MarcoB — DarkBulle, Commented Mar 17, 2021 at 14:40
my states are not ordered from 1 to 6000000 as you can see in my miniversion of N, they are "random" 14 digits integers, that is why I use notation $x_i$, instead of $i$, For example,the {15532192698680,17313748593344 } entry of matrix $M$ is -1.35158, i.e. the first number in the list of couplings of state 15532192698680 in $C$ , is the coupling to the first neighbour of state 15532192698680 in $N$. — DarkBulle, Commented Mar 17, 2021 at 14:46
So basically, entry {x_i ,N [[key[[x_i]] ]] [[n]] }=C [[key[[x_i]] ]] [[n]] @MarcoB — DarkBulle, Commented Mar 17, 2021 at 14:52
I think I see where you are going. However, I am worried that, since your indices are huge, the array will be equally impossibly huge even in its sparse form though. — MarcoB, Commented Mar 17, 2021 at 15:15

Henrik Schumacher · Accepted Answer · 2021-03-17 15:36:42Z

Basically the following should do (replacing N by n and C by c):

SparseArray[
 Rule[
  Transpose[{
    Join @@ KeyValueMap[ConstantArray[#1, Length[#2]] &, n],
    Join @@ Values[n]
    }],
  Join @@ Values[c]
  ]
 ]

To problem is that your numbers are too large. The matrix has as many rows as the largest key in the association n. And a sparse array has to store at least one number per row (basically the accumulated number of nonzero entries per row). So for 14 digit numbers and $64$-bit integers (8 Byte per integer), this may require ((10^15 - 1.) 8)/2^40 = 7275.96 TeraByte. A bit too much for my machine.

But one can simply reorder the rows and columns to the front. Then the smallest nonzero square block of the reordered matrix can be obtained as follows:

allrows = Keys[n];
allcols = Join @@ Values[n];
allindices = Union[allrows, allcols];
repo = First /@ PositionIndex[DeleteDuplicates[allindices]];
A = SparseArray[
  Rule[
   Transpose[{
     Join @@ KeyValueMap[ConstantArray[repo[#1], Length[#2]] &, n],
     Lookup[repo, allcols]
     }],
   Join @@ Values[c]
   ],
  {1, 1} Length[allindices]
  ]

That is, this matrix $A$ is basically the upper left block of $\tilde A = P^{-1} M P$ with a permutation matrix $P$. Of course, one has $$ \tilde{A}^k = (P^{-1} M\, P)^k = P^{-1} M^k P, $$ so this should not interfere with you goal of computing powers of $M$. If $x$ is your vector and if I denote the set of relevant indices allindices by $I$, then $y = M^k x$ is given as follows: $$ y_I = A^k x_I \qquad \text{and} \qquad y_{I^c} = 0. $$ Here $x_I$ and $y_I$ are the vectors obtained by reading off the entries of $x$ and $y$ that belong to $I$ and $y_{I^c}$ is the remainder.

Edit

The input is already almost in CSR format. So the following piece of code, which employs an undocumented constructor routine, should be a bit faster:

A = With[{
  dims = {1, 1} Length[allindices],
  rp = Prepend[Accumulate[Lookup[Length /@ n, allindices, 0]], 0],
  ci = Partition[Lookup[repo, allcols], 1],
  vals = Join @@ Values[c]
  },
 SparseArray @@ {Automatic, dims, 0, {1, {rp, ci}, vals}}
 ]

Beware that this will return only the correct result of there are no duplicates in any value of the association n.

Thank you @Henrik, I do not have the capacity to check your code right now, regarding the last remark about duplicates, does it only refer to the last bit of code, or to your whole answer ? I can not guarantee that no two state share exactly the same "neighbours", I'll have to think about it. — DarkBulle, Commented Mar 17, 2021 at 18:00
The remark about duplicates only refered the the last part. Simply use the second code block if you have duplicates. — Henrik Schumacher, Commented Mar 17, 2021 at 18:02

Stack Exchange Network

Fastest way to convert two associations into a sparse matrix

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged
performance-tuning
associations
sparse-arrays
or ask your own question.

Hot Network Questions

Fastest way to convert two associations into a sparse matrix

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged performance-tuningassociationssparse-arrays or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
performance-tuning
associations
sparse-arrays
or ask your own question.