The paper deals with the solution of complex linear systems \(A(\lambda)X(\lambda)=B(\lambda)\) where \(B(\lambda)\) is a polynomial vector and \(A(\lambda)\) a trigonometric matrix polynomial. The paper discusses several (non-orthogonal) direct methods for the solution of linear systems which are adapted to the polynomial situation and backward rounding error analysis is given. The method of truncated systems and the are treated explicitly. For other methods like Jordan elimination, optimum elimination, and the cutting algorithm, complexity results and bounds for backward rounding errors are given without deriving them.