  Gr{\"o}bner bases is one the most powerful tools in algorithmic non-linear
algebra. Their computation is an intrinsically hard problem with a complexity
at least single exponential in the number of variables. However, in most of the
cases, the polynomial systems coming from applications have some kind of
structure. For example , several problems in computer-aided design, robotics,
vision, biology , kinematics, cryptography, and optimization involve sparse
systems where the input polynomials have a few non-zero terms. Our approach to
exploit sparsity is to embed the systems in a semigroup algebra and to compute
Gr{\"o}bner bases over this algebra. Up to now, the algorithms that follow this
approach benefit from the sparsity only in the case where all the polynomials
have the same sparsity structure, that is the same Newton polytope. We
introduce the first algorithm that overcomes this restriction. Under regularity
assumptions, it performs no redundant computations. Further, we extend this
algorithm to compute Gr{\"o}bner basis in the standard algebra and solve sparse
polynomials systems over the torus $(C*)^n$. The complexity of the algorithm
depends on the Newton polytopes.
