Solving Quartic Equation with a Coefficient of $1$ MB Space

Question

I have an equation of $4$ degree (Quartic equation)and a coefficient of this equation takes $1$ megabyte space in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to get rational solution with the exact numerator and the exact denominator (not the approximation). Is it possible?

There are are programming languages (e.g. MAGMA), computer algebra systems (e.g. PARI/GP, SageMath etc, here PARI is C library, can be called from a high-level language application ,for instance, written in C, C++, Pascal, Fortran, Perl, or Python).

If possible, then which programming language or computer algebra systems or library or softaware will be best to solve the Quartic equation as described above? What are the additional issues (configurations of RAM, Processor)?

Answer 1

I think you can use PARI/GP to do the job if you have enough RAM and CPU time. You can use the factor() function. Of course, you have to read the coefficients from the text file first, for example, using the readvec() function. Then construct a polynomial from those coefficients using the Pol() function.

Here is a very simple example of what gp can do with a quartic polynomial:

> V = readvec("coeff.txt");
> print(V)
[5, -22, 11, 19, -7]
> P = Pol(V);  
> print(P)
5*x^4 - 22*x^3 + 11*x^2 + 19*x - 7
> print(factor(P))
[5*x - 7, 1; x^3 - 3*x^2 - 2*x + 1, 1]
> print(polroots(P))
[-0.83424 + 0.E-9*I, 0.34338 + 0.E-9*I, 1.4000 + 0.E-9*I, 3.4909 + 0.E-9*I]~

The quartic $P$ has integer coefficients. It has a linear factor of $\,5x-7\,$ which implies that one root is $\,x = 7/5 = 1.4\,$ and the the other factor is an irreducible cubic. The printing of the roots of the polynomial confirms that $\,1.4\,$ is a root. If you want, you can call the PARI library from a high-level language as you suggested. You will get essentially the same results.

Answer 2

A long comment:

These computer algebra systems are usually not optimized for solving equations with such great coefficients. However, I haven't tested whether they could handle such cases.

My suggestion would be to write your own program, with the support of some arbitrary precision number system (e.g. gmp).

Also, as a first step, perform a decomposition modulo various (small) prime numbers to "guess" the nature of the final decomposition (e.g. is it a product of four linear factors, or two quadratic factors, etc.). This step can be done very fast, while giving quite useful information.

If, for example, it turns out that the quartic has four linear factors, then you may just apply the well known methods for solving quatic equations.