Questions & explanations
1. Compute the discriminant of a quadratic polynomial using a resultant.
The discriminant of a polynomial f(x)=ax^2+bx+c is b^2-4ac. It tells if the roots are real and distinct. It can be computed as the resultant of f and its derivative f'=2ax+b. The resultant of f and f' is a^2 times the discriminant. For f=ax^2+bx+c, the Sylvester matrix is 3x3: rows of f: [a,b,c]; rows of f': [2a,b,0]; and [0,2a,b]. Determinant = a*(b^2-4ac). So discriminant = resultant/(a^2?) Actually resultant = a^{deg f'}= a^2 * discriminant? Let's compute: The resultant is det = a*(b^2-4ac). Divide by a to get discriminant? Standard: discriminant = (-1)^{n(n-1)/2}/a_n * resultant(f,f'). For n=2, (-1)^{1}= -1, so discriminant = -1/a * resultant = -1/a * a*(b^2-4ac) = -(b^2-4ac)?? That gives negative. Actually correct: discriminant = (b^2-4ac) = (-1)^{2*1/2}/a * resultant = 1/a * resultant? Check: resultant of f and f' = (-1)^{n(n-1)/2} a_n^{n-2} * discriminant? For n=2: (-1)^1 a^{0} = -1, so resultant = - discriminant? This is messy. Better to use the known formula: discriminant = (b^2-4ac). The resultant of f and f' is -a*(b^2-4ac). So indeed discriminant = -resultant/a. So symbol
2. What is the difference between a reduced Gröbner basis and a minimal Gröbner basis?
A minimal Gröbner basis has the smallest possible leading terms: no leading term divides another, and each polynomial is reduced with respect to the others except for its own term. A reduced Gröbner basis goes further: each polynomial is fully reduced, meaning no monomial in it can be reduced by the leading terms of the others. For example, {x^2, xy, y^2} is minimal but not reduced because xy can be reduced by x^2? Actually check: x^2 does not divide xy? Leading terms: x^2, xy, y^2. Reduced requires that in each polynomial, no term is divisible by any leading term of others. In xy, term xy is divisible by itself? Usually the leading term is excluded. So reduced version might be {x^2, xy, y^2} is already reduced? Actually typical reduced basis has each polynomial's leading coefficient 1. So minimal + leading coefficients 1 + each polynomial reduced means reduced. Most algorithms compute reduced Gröbner bases.
3. How do you build the Sylvester matrix for two polynomials f and g?
Suppose f(x)=a_n x^n + ... + a_0 and g(x)=b_m x^m + ... + b_0. The Sylvester matrix is (n+m) by (n+m). The first m rows contain shifted coefficients of f: row 1: [a_n, a_{n-1}, ..., a_0, 0,...,0]; row 2: [0, a_n, ..., a_0, 0,...0]; etc. The next n rows contain shifted coefficients of g. For example, f=2x^2+3x+1, g=x-2: n=2,m=1. Matrix: rows from f: [2,3,1] and [0,2,3,1? Actually size 3x3: first row [2,3,1]; second row [0,2,3? wait need 3 columns? Let's do properly: f degree 2, g degree 1, matrix 3x3. f rows: row1: [2,3,1]; row2: [0,2,3]? Actually shifted: for f we have m=1 row: row of f: [2,3,1] but then need 1 row from f? Mist. Standard: matrix has m rows of f coefficients and n rows of g coefficients. So for f degree n=2, g degree m=1, we have m=1 row of f: [2,3,1]. Then n=2 rows of g: row1: [1,-2,0]; row2: [0,1,-2]. Determinant gives resultant. This method works for any degrees.
4. Give an example of using Sturm's theorem to count the number of real roots of the polynomial x^2 - 2 in the interval [0,2].
Let p(x)=x^2-2. p'(x)=2x. Sturm sequence: p0 = x^2-2, p1 = 2x, p2 = -remainder(p0/p1). Divide x^2-2 by 2x: quotient = x/2, remainder = -2, so p2 = -(-2)=2. So sequence: x^2-2, 2x, 2. Evaluate at a=0: p0(0)=-2 (negative), p1(0)=0 (we treat zero as neither sign? Usually sign is taken from limit? But for 0, the sign of p1 is considered positive? Actually careful: In Sturm's theorem, you consider sign changes ignoring zeros. But for simplicity, at 0, we have signs: -2 (neg), 0 (neglect), 2 (pos). Typically you take sign from left and right? Best to avoid zero. Instead choose a=1 and b=2. At a=1: p0=-1 (neg), p1=2 (pos), p2=2 (pos) => signs: -,+,+ => 1 sign change. At b=2: p0=2 (pos), p1=4 (pos), p2=2 (pos) => 0 changes. Difference = 1, meaning one root in (1,2). Indeed sqrt(2)~1.414 is in (1,2).
5. Compare the memory and time requirements of FDTD and FEM for a typical 3D simulation.
FDTD on a uniform grid requires memory proportional to the number of cells, and each time step updates all cells. For a problem of size 100x100x100 cells, it needs about 24 million variables (6 field components) and takes maybe 1 second per 1000 time steps on a modern GPU. FEM uses unstructured grids, so memory depends on the number of elements and unknowns. For the same volume, FEM can use fewer elements if the geometry is simple, but each element has a matrix. FEM often needs solving a sparse linear system, which is more memory-intensive and slower per frequency point. For broadband, FDTD is faster; for high accuracy on complex shapes, FEM may be better.
6. What is hybrid symbolic-numeric computation?
Hybrid symbolic-numeric computation combines algebraic (symbolic) methods with numerical approximation to solve problems accurately and efficiently. For example, solving polynomial systems exactly is often impossible, so numeric methods give approximate roots, but symbolic techniques can simplify or certify results. Hybrid algorithms use symbolic preprocessing like Gröbner bases to reduce the problem, then numeric continuation for roots. They also use symbolic error bounds to ensure numeric results are correct. This approach is used in robotics, control theory, and computer-aided design. It balances the strengths of both worlds.
7. Compare bit complexity and algebraic complexity in computer algebra.
Algebraic complexity counts operations in a field (e.g., +, ×) assuming infinite precision. Bit complexity counts bit operations, accounting for number size. For example, multiplying two degree-n polynomials with integer coefficients of size k bits: algebraic complexity is O(n log n) field operations, but bit complexity is O(n log n log(kn)) due to coefficient growth. In computer algebra, bit complexity is more realistic for exact computation. Many algorithms use modular techniques to control coefficient growth, trading algebraic operations for bit operations. Both measures are important, but bit complexity is harder to analyze.
8. How does parallelization of polynomial multiplication work?
Parallel multiplication of two dense polynomials can be done by splitting the coefficient arrays. For example, using FFT algorithms, the transform can be parallelized over frequencies. Alternatively, the product polynomial's coefficients can be computed independently via convolution threads. Each thread handles a range of output degrees. For sparse polynomials, techniques like hash tables distribute monomial products across processes. This works well on shared memory. Distributed memory requires partitioning of the exponent space. The speedup is nearly linear for large degrees because the work per coefficient is independent.
9. Compare the symbolic derivation of the Black-Scholes formula using the risk-neutral approach versus solving the PDE.
The risk-neutral approach uses expected value: option price = e^(-rT)*E[max(S_T - K,0)] under a probability measure where the stock grows at rate r. Symbolically, this expectation becomes an integral over the lognormal distribution. That integral simplifies to the Black-Scholes formula. The PDE approach solves a differential equation with boundary conditions. Both give the same formula. Symbolic computation can handle both: one does integration, the other does differential equation solving. The PDE method is more general for exotic options, while the expectation method is intuitive. Both confirm the same final expression.
10. Give a simple example where Gosper's algorithm finds a closed form.
Consider the sum S(n) = sum_{k=0}^n (-1)^k / (k+1). Gosper's algorithm checks if the term is hypergeometric. Here, the term t_k = (-1)^k/(k+1) is hypergeometric because the ratio t_{k+1}/t_k = -(k+1)/(k+2) is a rational function. The algorithm finds a closed form: S(n) = 1 - (-1)^{n+1}/(n+2) times something? Actually, Gosper's algorithm finds that there is no simple closed form for indefinite hypergeometric sums unless certain conditions hold. For this sum, it returns failure, meaning no elementary closed form exists. But for t_k = 1/(k(k+1)), Gosper's algorithm gives -1/(k+1) as the indefinite sum, so S(n) = 1 - 1/(n+1).
11. What does it mean when the Jacobian matrix is singular in Newton's method?
The Jacobian matrix is a square matrix of first partial derivatives. When it is singular, its determinant is zero, meaning the matrix cannot be inverted. In Newton's method for solving polynomial systems, we need to solve a linear system with the Jacobian. If the Jacobian is singular, that linear system may have no solution or many solutions. This often happens near a singular solution, where the system's equations are not independent. For example, the system x^2 = 0 has a singular solution at x=0 because the Jacobian is 2x, which is zero at the root. A singular Jacobian causes Newton's method to fail or converge slowly.
12. How does Zeilberger's algorithm extend Gosper's algorithm?
Zeilberger's algorithm, or creative telescoping, finds a recurrence for the sum S(n) of a hypergeometric term t(n,k). It extends Gosper's algorithm by looking for a rational function R(n,k) such that t(n,k) = G(n,k+1) - G(n,k) after scaling. It finds a recurrence like a_0(n)S(n) + a_1(n)S(n+1) + ... = 0. Gosper's algorithm only gives a closed form for a single sum, while Zeilberger's gives a recurrence that holds for all n. This recurrence can then be solved to get the closed form if possible. For example, for the binomial sum sum_k C(n,k), Zeilberger's algorithm yields the recurrence S(n+1)=2S(n), leading to S(n)=2^n.