  The Lenstra-Lenstra-Lov\'asz (LLL) algorithm is the most practical lattice
reduction algorithm in digital communications. In this paper, several variants
of the LLL algorithm with either lower theoretic complexity or fixed-complexity
implementation are proposed and/or analyzed. Firstly, the $O(n^4\log n)$
theoretic average complexity of the standard LLL algorithm under the model of
i.i.d. complex normal distribution is derived. Then, the use of effective LLL
reduction for lattice decoding is presented, where size reduction is only
performed for pairs of consecutive basis vectors. Its average complexity is
shown to be $O(n^3\log n)$, which is an order lower than previously thought. To
address the issue of variable complexity of standard LLL, two fixed-complexity
approximations of LLL are proposed. One is fixed-complexity effective LLL,
while the other is fixed-complexity LLL with deep insertion, which is closely
related to the well known V-BLAST algorithm. Such fixed-complexity structures
are much desirable in hardware implementation since they allow straightforward
constant-throughput implementation.
