  We present two new algorithms for the computation of the q-integer linear
decomposition of a multivariate polynomial. Such a decomposition is essential
for the treatment of q-hypergeometric symbolic summation via creative
telescoping and for describing the q-counterpart of Ore-Sato theory. Both of
our algorithms require only basic integer and polynomial arithmetic and work
for any unique factorization domain containing the ring of integers. Complete
complexity analyses are conducted for both our algorithms and two previous
algorithms in the case of multivariate integer polynomials, showing that our
algorithms have better theoretical performances. A Maple implementation is also
included which suggests that our algorithms are also much faster in practice
than previous algorithms.
