Improve speed and memory use in the construction of linear combinations of two lists

Question

I have two lists, list1 and list2, for instance

list1=RandomReal[{-10,10},500]
list2=RandomReal[{-10,10},600]

and two sets of coefficients,

coeffs1={-1,-0.618,0.618}
coeffs2={0.618,-0.618,-1}

From these, I would like to generate a nested list of elements where

newList[[i,1]]=coeffs1[[i]] list1 + coeffs2[[i]] list2[[1]]
newList[[i,2]]=coeffs1[[i]] list1 + coeffs2[[i]] list2[[2]]
...
newList[[i,-1]]=coeffs1[[i]] list1 + coeffs2[[i]] list2[[-1]]

That is, I want every linear combination of one element from list1 and one from list2 and grouped first by the index of the coefficient in the linear combination coeffs1 and coeffs2, then by the index of the element in the combination from list2. The most straightforward way to do this would be:

newList=Table[coeffs1[[i]] list1[[j]]+coeffs2[[i]] list2[[k]],{i,1,3},{j,1,Length@list1},{k,1,Length@list2}]

But this is far too slow (it can be sped up significantly with Compile, but its scaling behaviour for large lists still makes it undesirable). Alternatively, I could use some list manipulation:

meshgrid = {ConstantArray[list1, Length@list2], Transpose@ConstantArray[list2, Length@list1]};
newList=Transpose/@Table[coeffs1[[ii]] meshgrid[[1]] + coeffs2[[ii]] meshgrid[[2]], {ii,3}]

which is significantly faster, but still slower than I'd like and probably requires much more memory than the first method because of meshgrid. The length of list1 and list2 is going to be around 1500, and the code will be part of a loop that is run many thousands of times, so I would like the code to be as fast as possible (while secondarily minimizing the memory used) in the construction of newList. Is there a better way to do this?

Also, I'm mostly interested in the case Length[list1]==Length[list2], if this can be taken advantage of in any way.

Answer 1

list1 = RandomReal[{-10, 10}, 500];
list2 = RandomReal[{-10, 10}, 600];
coeffs1 = {-1., -0.618, 0.618};
coeffs2 = {0.618, -0.618, -1.};

First@RepeatedTiming[
  newList = 
    Table[coeffs1[[i]] list1[[j]] + coeffs2[[i]] list2[[k]], {i, 1, 
      3}, {j, 1, Length@list1}, {k, 1, Length@list2}];
  ]

First@RepeatedTiming[
  meshgrid = {ConstantArray[list1, Length@list2], 
    Transpose@ConstantArray[list2, Length@list1]}; 
  newList2 = 
   Transpose /@ 
    Table[coeffs1[[ii]] meshgrid[[1]] + 
      coeffs2[[ii]] meshgrid[[2]], {ii, 3}];
  ]

First@RepeatedTiming[
  newList3 = MapThread[
     Outer[Plus, ##] &,
     {
      KroneckerProduct[coeffs1, list1],
      KroneckerProduct[coeffs2, list2]
      }
     ];
  ]

Max[Abs[newList - newList2]]
Max[Abs[newList - newList3]]

0.90022

0.0013152

0.000390233

0.

0.

Answer 2

First we create the data:

n = 500;
list1 = RandomReal[{-10, 10}, n];
list2 = RandomReal[{-10, 10}, n];
coeffs1 = {-1, -0.618, 0.618};
coeffs2 = {0.618, -0.618, -1};

Then we create the first and second part of the result and add them:

t1 = (ConstantArray[#, n] & /@ list1) # & /@ coeffs1;
t2 = (ConstantArray[#, n] & /@ list2 // Transpose) # & /@ coeffs2;

res = t1 + t2;

To check we take your lengthy expression and compare the result to the above:

res1 = Table[ 
   coeffs1[[i]] list1[[j]] + coeffs2[[i]] list2[[k]], {i, 1, 3}, {j, 
    1, Length@list1}, {k, 1, Length@list2}];

res == res1

(* True*)