How to efficiently compute the minimal polynomial of a number expressed in radicals?

$\color{brown}{\textbf{The new version.}}$

Each radical $\sqrt[k]a$ forms an array of the variables $(1, p, p^2,\dots, p^{k-1}),$ wherein there is not a problem to exclude them via a homogenius linear system.

From the expression $\color{brown}{\mathbf{\ x=\sqrt[k] a}}\ $ should

$$ \begin{cases} x-p_j = 0\\ p_j = \sqrt[k]a\, \omega_k^j\\ \omega_k = e^{^{\Large\frac{2\pi i}k}} \end{cases}\Rightarrow \begin{cases} \prod\limits_{j=0}^{m-1}(x-p_j) = 0\\ p_j = \sqrt[k]a\, \omega_k^j\\ j=0\dots k-1\\ \omega_k = e^{^{\Large\frac{2\pi i}k}} \end{cases}\Rightarrow x^k-a = 0. $$

From the expression $\color{brown}{\mathbf{\ x=\sqrt a + \sqrt[3]b}}\ $ should $$ \begin{cases} x-q \pm \sqrt a = 0\\ q^3 = b \end{cases}\Rightarrow \begin{cases} (x-q+\sqrt a)(x-q+\sqrt a) = 0\\ q^3 = b \end{cases}\Rightarrow \begin{cases} (x-q_j)^2 - a = 0\\ q_j = \sqrt[3]b\omega_3^j\\ \omega_3 = e^{^{\Large\frac{2\pi i}3}}, \end{cases} $$$$ \begin{align} &\Big((x-\sqrt[3]{b})^2-a\Big)\Big((x-\sqrt[3]{b}\,\omega_3)^2-a\Big) \Big((x-\sqrt[3]{b}\,\omega_3^2)^2-a\Big) = 0,\\[4pt] &\Big((x-\sqrt[3]{b})(x-\sqrt[3]{b}\,\omega_3)(x-\sqrt[3]{b}\,\omega_3^2)\Big)^2\\[4pt] &-a\Big((x-\sqrt[3]{b})^2(x-\sqrt[3]{b}\,\omega_3)^2 +(x-\sqrt[3]{b}\,\omega_3)^2(x-\sqrt[3]{b}\,\omega_3^2)^2+ (x-\sqrt[3]{b}\,\omega_3^2)^2 (x-\sqrt[3]{b})^2\Big)\\[4pt] &+ a^2\Big((x-\sqrt[3]{b})^2 + (x-\sqrt[3]{b}\,\omega_3)^2 + (x-\sqrt[3]{b}\,\omega_3^2)^2\Big) -a^3 =0,\\[4pt] &(x^3-b)^2-3ax(x^3+2b)+3a^2x^2-a^3 =0,\\[4pt] &x^6 - 3ax^4 - 2bx^3 + 3a^2x^2 - 6abx + b^2 - a^3 = 0 \end{align}$$ (see also WA result).

From the expression $\color{brown}{\mathbf{\ z=\sqrt a + \sqrt[3]b + \sqrt[4]c + \sqrt[5]d,\ }}$ should

$$ \begin{cases} z-p-q-r-s = 0\\ p^2=a\\ q^3 = b\\ r^4 = c\\ s^5 = d \end{cases}\Rightarrow \begin{cases} x = p+q = z-r-s\\ f_2(x) = x^6 - 3ax^4 - 2bx^3 + 3a^2x^2 - 6abx + b^2 - a^3 = 0\\ r^4 = c\\ s^5 = d \end{cases}\Rightarrow \begin{cases} y = x+r = z-s\\ f_3(y) = \prod\limits_{j=0}^3 f_2(y-r_j) = 0\\ r_j = \sqrt[4]c\, i^j\\ s^5 = d, \end{cases} $$

$f_3(y)=$

(see WA result).

Alternative approaches are considered below.

$\color{brown}{\textbf{The old version.}}$

Each radical $\sqrt[k+1]a$ forms an array of the variables $(p, p^2,\dots, p^k),$ wherein there is not a problem to exclude them via a homogenius linear system.

In particular, for the expression $\color{brown}{\mathbf{\ x=\sqrt a + \sqrt[3]b}}\ $ easily to get

$$ \begin{cases} p+q-x = 0\\ p^2=a\\ q^3 = b \end{cases}\Rightarrow \begin{cases} p+q-x = 0\\ a + p(q-x) = 0\\ q^3 = b \end{cases}\Rightarrow \begin{cases} \begin{vmatrix} 1 & q-x \\ q-x & a \end{vmatrix} = 0\\ q^3 =b\end{cases} $$$$ \begin{cases} q^2-2xq+x^2 - a = 0\\ b-2xq^2+(x^2-a)q = 0\\ bq - 2bx + (x^2-a) q^2 = 0 \end{cases}\Rightarrow \begin{vmatrix} 1 & - 2x & x^2 - a\\ -2x & x^2-a & b\\ x^2-a & b & -2bx \end{vmatrix} = 0, $$$$ x^6 - 3ax^4 - 2bx^3 + 3a^2x^2 - 6abx + b^2 - a^3 = 0 $$ (see also WA result).

"Brite force" way is $$ \begin{cases} p+q-x = 0\\ a+pq-px = 0\\ pq+q^2-qx = 0\\ aq+pq^2-pqx = 0 \\ pq^2+b-q^2x = 0\\ aq^2+bp-pq^2x = 0 \end{cases}\Rightarrow \begin{pmatrix} -x & 1 & 1 & 0 & 0 & 0\\ a & -x & 0 & 1 & 0 & 0\\ 0 & 0 & -x & 1 & 1 & 0\\ 0 & 0 & a & -x & 0 & 1\\ b & 0 & 0 & 0 & -x & 1\\ 0 & b & 0 & 0 & a & -x\ \end{pmatrix} \begin{pmatrix} 1\\p\\q\\pq\\q^2\\pq^2 \end{pmatrix}= 0, $$$$ \begin{vmatrix} -x & 1 & 1 & 0 & 0 & 0\\ a & -x & 0 & 1 & 0 & 0\\ 0 & 0 & -x & 1 & 1 & 0\\ 0 & 0 & a & -x & 0 & 1\\ b & 0 & 0 & 0 & -x & 1\\ 0 & b & 0 & 0 & a & -x\ \end{vmatrix} =\begin{vmatrix} 1 & 0 & 0 & 0 &-x & 1 \\ 0 & 1 & 0 & 0 & a &-x \\ -x & 1 & 1 & 0 & 0 & 0 \\ a &-x & 0 & 1 & 0 & 0 \\ 0 & 0 &-x & 1 & b & 0 \\ 0 & 0 & a &-x & 0 & b \end{vmatrix} $$$$ =\begin{vmatrix} 1 & 0 & 0 & 0 &-x & 1 \\ 0 & 1 & 0 & 0 & a &-x \\ 0 & 1 & 1 & 0 &-x^2 & x \\ 0 &-x & 0 & 1 & ax &-a \\ 0 & 0 &-x & 1 & b & 0 \\ 0 & 0 & a &-x & 0 & b \end{vmatrix} =\begin{vmatrix} 1 & 0 & 0 & a &-x \\ 0 & 1 & 0 &-x^2-a & 2x \\ 0 & 0 & 1 & 2ax &-x^2-a \\ 0 &-x & 1 & b & 0 \\ 0 & a &-x & 0 & b \end{vmatrix} $$$$ =\begin{vmatrix} 1 & 0 &-x^2-a & 2x \\ 0 & 1 & 2ax &-x^2-a \\ 0 & 1 & b-x(x^2+a) & -2x^2 \\ 0 &-x & a(x^2+a) & b-2ax \end{vmatrix} =\begin{vmatrix} 1 & 2ax &-x^2-a \\ 0 & b-x(x^2+3a) & -x^2+a \\ 0 & a(3x^2+a) & b-x(x^2+3a) \end{vmatrix} $$$$ =\begin{vmatrix} b-x(x^2+3a) & -x^2+a \\ a(3x^2+a) & b-x(x^2+3a) \end{vmatrix}=0, $$$$ x^6 - 3ax^4 - 2bx^3 + 3a^2x^2 - 6abx + b^2 - a^3 = 0. $$

If $\color{brown}{\mathbf{\ x=\sqrt a + \sqrt[3]b + \sqrt[4]c + \sqrt[5]d,\ }}$ then

$$ \begin{cases} p+q+r+s-x = 0\\ p^2=a\\ q^3 = b\\ r^4 = c\\ s^5 = d \end{cases}\Rightarrow \begin{cases} x_1 = x-q-r-s\\ p-x_1 = 0\\ a - px_1 = 0\\ q^3 = b\\ r^4 = c\\ s^5 = d \end{cases}\Rightarrow \begin{cases} \begin{vmatrix} 1 & -x_1 \\ -x_1 & a \end{vmatrix} = 0\\ q^3 = b\\ r^4 = c\\ s^5 = d, \end{cases} $$$$ \begin{cases} x_2 = x - r - s = x_1+q\\ q^2-2x_2q+(x_2^2 - a) = 0\\ b-2x_2q^2+(x_2^2-a)q = 0\\ bq - 2bx_2 + (x_2^2-a) q^2 = 0\\ r^4 = c\\ s^5 = d \end{cases}\Rightarrow \begin{cases} f_2(x_2) = \begin{vmatrix} 1 & - 2x_2 & x_2^2 - a\\ -2x_2 & x_2^2-a & b\\ x_2^2-a & b & -2bx_2 \end{vmatrix} = 0\\ r^4 = c\\ s^5 = d, \end{cases} $$$$ \begin{cases} x_3 = x - s = x_2+r\\ f_2(x_2) = x_2^6 - 3ax_2^4 - 2bx_2^3 + 3a^2x_2^2 - 6abx_2 + b^2 - a^3 = 0\\ f_2(x_3-r) = 0\\ r^4 = c\\ s^5 = d, \end{cases} $$$$ \begin{cases} x_3 = x - s = x_2+r\\[4pt] r^6 + f_{25} r^5 + f_{24} r^4 + f_{23} r^3 + f_{22} r^2 + f_{21} r + f_{20} = 0\\[4pt] f_{25} = \dfrac1{5!}\dfrac{\partial^5}{\partial r^5}f_2(x_3-r)\bigg|_{r=0} = -6x_3\\[4pt] f_{24} = \dfrac1{4!}\dfrac{\partial^4}{\partial r^4}f_2(x_3-r)\bigg|_{r=0} = 15x_3^2-3a\\[4pt] f_{23} = \dfrac1{3!}\dfrac{\partial^3}{\partial r^3}f_2(x_3-r)\bigg|_{r=0} = -\dbinom63 x_3^3 + 3a\dbinom43 x_3 + 2b = -20x^3 + 12ax +2b\\[4pt] f_{22} = \dfrac1{2!}\dfrac{\partial^2}{\partial r^2}f_2(x_3-r)\bigg|_{r=0} = \dbinom62x_3^4 - 3a\dbinom42x_3^2 - 2b\dbinom32x_3 +3a^2\\[4pt] = 15x_3^4 - 18a x_3^2 - 6bx_3 + 3a^2\\[4pt] f_{21} = -\dfrac{\partial}{\partial r}f_2(x_3-r)\bigg|_{r=0} = - 6x_3^5 + 12ax_3^2 + 6bx_3^2 - 6a^2x_3 + 6ab\\[4pt] f_{20} = f_2(x_3) = x_3^6 - 3ax_3^4 - 2bx_3^3 + 3a^2x_3^2 - 6abx_3 + b^2 - a^3\\[4pt] r^4 = c\\[4pt] s^5 = d, \end{cases} $$$$ \begin{cases} x_3 = x - s = x_2+r\\[4pt] f_{23} r^3 + (f_{22}+c) r^2 + (f_{21}+cf_{25}) r + (f_{20} + cf_{24}) = 0\\[4pt] cf_{23} + (f_{22}+c) r^3 + (f_{21}+cf_{25}) r^2 + (f_{20} + cf_{24}) r = 0\\[4pt] cf_{23} r + c(f_{22}+c) + (f_{21}+cf_{25}) r^3 + (f_{20} + cf_{24}) r^2 = 0\\[4pt] cf_{23} r^2 + c(f_{22}+c) r + c(f_{21}+cf_{25}) + (f_{20} + cf_{24}) r^3 = 0\\[4pt] s^5 = d, \end{cases} $$

and this leads to the determinant of a Toeplitz matrix $$ f_3(x) = \begin{vmatrix} f_{20} + cf_{24} & f_{21} + cf_{25} & f_{22}+c &f_{23} \\ cf_{23} & f_{20} + cf_{24} & f_{21}+cf_{25} & f_{22}+c \\ cf_{22}+c^2 & cf_{23} & f_{20}+cf_{24} & f_{21}+cf_{25} \\ cf_{21}+c^2f_{25} & cf_{22}+c^2 & cf_{23} & f_{20}+cf_{24} \end{vmatrix} = 0,\tag1 $$ where

$${\small\begin{cases} f_{25} = -6(x-s) \\[4pt] f_{24} = 15(x-s)^2 - 3a \\[4pt] f_{23} =-20(x-s)^3 + 12a(x-s) + 2b \\[4pt] f_{22} = 15(x-s)^4 - 18a(x-s)^2 - 6b(x-s) + 3a^2 \\[4pt] f_{21} = -6(x-s)^5 + 12a(x-s)^2 + 6b(x-s)^2 - 6a^2(x-s) + 6ab \\[4pt] f_{20} = (x-s)^6 - 3a(x-s)^4 - 2b(x-s)^3 + 3a^2(x-s)^2 - 6ab(x-s) + b^2 - a^3. \end{cases}}\tag2$$

Computation complexity of this approach can be defined as $$\sum\limits_{i} D(k_i),$$ where $D(k)$ is the computation complexity of the determinant $k\times k.$

It is less than the OP estimation.

Since the Groebner basis algorithm has a great computational complexity and the manipulations approach cannot be easily formalized, this approach looks the fastest of the proposed variants.