function [tt] = tt_qtoepl(x, d)

% returns the multilevel Toeplitz matrix tt generated by the multi-dimensional input vector x 
% in the QTT format
%
% The size of the input vector is 2^(d(1) + 1) x ... x 2^(d(D) + 1),
% The output matrix is square of order 2^d(1) x ... x 2^d(D).
% The (i_1,...i_D)-th component of x is not used if at least one of i_1,...,i_D is equal to 1
% (e. g., in the one-dimensional case the first component of x is not used)
%
% April 20, 2011
% Vladimir Kazeev
% vladimir.kazeev@gmail.com
% INM RAS
% Moscow, Russia
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% For details please see the preprint
% http://www.mis.mpg.de/publications/preprints/2011/prepr2011-36.html
% Vladimir A. Kazeev, Boris N. Khoromskij and Eugene E. Tyrtyshnikov
% Multilevel Toeplitz matrices generated by QTT tensor-structured vectors and convolution with logarithmic complexity
% January 12, 2012
% Vladimir Kazeev,
% Seminar for Applied Mathematics, ETH Zurich
% vladimir.kazeev@sam.math.ethz.ch
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

D = numel(d);
tt = tt_qshiftstack(d);

sz=[];
for K=1:D
	sz = [sz; 4*ones(d(K),1), 2*ones(d(K),1); 1, 2];
end

tt = tt_qreshape(tt, 3, sz);
tt = tt_matrix(tt) * x;


tt1 = cell(sum(d),1);
ind = 0;
ind1 = 0;
for K = 1:D
	for k = 1:d(K)-1
		tt1{ind1 + k} = tt{ind + k};
	end	
	
	p = size(tt{ind + d(K)}, 1);
	q = size(tt{ind + d(K)}, 3);
	r = size(tt{ind + d(K) + 1}, 3);
	tt1{ind1 + d(K)} = reshape(reshape(permute(tt{ind+d(K)},[2, 1, 3]),[4*p,q])*...
        reshape(permute(tt{ind+d(K)+1},[2, 1, 3]),[q,r]),[4,p,r]);
    tt1{ind1 + d(K)} = permute(tt1{ind1 + d(K)}, [2, 1, 3]);
	ind=ind+d(K)+1;
	ind1=ind1+d(K);
end
tt = tt1;
tt1 = tt_tensor;
tt = cell2core(tt1, tt);
tt = tt_matrix(tt);
return
end
