Is there anything like this for multivariate polynomials? To keep things simple: is there a "companion" matrix for quadratic or cubic bivariate polynomial? And is it possible to employ some eigenvalue algorithm for find all of its roots?
In general you can't find all of multivariate polynomial roots. You can factor it, but the factorization is in general not unique and you won't be getting just one root per factor. For example $$x^2+y^2 - 1=0$$ has solutions all along the unit circle so that would be an infinite number of roots. But if you have $$x^3+xy^2-x =0$$ of course you can write it as $$x(x^2+y^2-1)=0$$ which is the selection between a line of $0$ for an $x$ and said circle.