Name

maxmod — find the maximum modulus of a complex polynomial on the unit disc.

Synopsis

#include "maxmod.h";
extern int maxmod_d( const maxmod_complex_t *coeffs,
  size_t order,
  maxmod_opt_t options,
  maxmod_results_t * results);
 
extern maxmod_float_t maxmod( const maxmod_complex_t *coeffs,
  size_t order);
 

DESCRIPTION

The maxmod and maxmod_d functions calculate the maximum modulus of a complex polynomial on the unit disc. The maxmod function offers a simplified interface while maxmod_d gives access to a detailed interface.

For both functions the first two parameters are the coefficients and order of the polynomial. Thus the coefficients varname is an array of order+1 complex values.

For the maxmod_d function the third parameter is a structure maxmod_opt_t discussed below. The final argument is a pointer to a maxmod_results_t structure.

ARITHMETIC TYPES

The maxmod function operates with abstracted data types which can be chosen a compile-time, see the section on MACROS below.

The types are maxmod_int_t, a signed integer type; maxmod_float_t, a floating point type and maxmod_complex_t, a complex type.

OPTIONS

The detailed interface uses a maxmod_opt_t structure to pass options to the function. The fields are:

maxmod_float_t relerror

The required relative accuracy in the result;

size_t max.evaluations

The maximum number of polynomial evaluations to be used in calculating the maximum modulus. If this number is exceeded then the function terminates early and returns MAXMOD_INACCURATE;

Use a value of zero for unlimited evaluations.

size_t max.intervals

An upper bound on the size of the interval table, behaving as max.evaluations.

RESULTS

The detailed interface returns its results in the maxmod_results_t passed to the function by reference. The fields are:

maxmod_float_t maxmod

The maximum modulus;

maxmod_float_t relerror

The relative error in the maximum modulus;

maxmod_float_t width

The width of each interval at the end of the processing;

size_t evaluations

The number of polynomial evaluation used.

RETURN VALUE

The simplified interface returns the estimate of the maximum modulus.

The detailed interface return an integer errorcode defined by the symbols:

MAXMOD_OK

Success;

MAXMOD_INACCURATE

The function terminated before the requested accuracy could be achieved. The results structure is modified to give the (inaccurate) estimate found;

MAXMOD_ERROR

An error occurred, the results structure is not modified.

MACROS

The integer, float and complex types used by the functions are determined by the (compile-time) macros:

MAXMOD_INT_LONG

If this symbol is defined the maxmod_int_t type is a long long int, if not it is a long int;

MAXMOD_FLOAT_LONG

If defined then the maxmod_float_t type is a long double, otherwise it is a double. The maxmod_complex_type is modified similarly;

MAXMOD_LONG

A utility macro which defines MAXMOD_INT_LONG and MAXMOD_FLOAT_LONG.

In the case that the code has been compiled into a library (the expected use-case) then these values are/were fixed at compile-time, so the values are forced-undefined by the header file. If compiling the code into your own project, then one can override this precaution by defining MAXMOD_STAND_ALONE.

ACCURACY

If the polynomial evaluation is exact then the algorithm should be able to obtain arbitrary accuracy. However, for floating point arithmetic the relative error in evaluating a polynomial is of the order of the relative error in representing a floating point value: around machine epsilon.

If the user specifies a required relative accuracy which of the order (or smaller) than machine epsilon then, in the closing stages of the algorithm, the polynomial evaluates as constant. This can lead to an exponential explosion in the number of intervals used eventually exhausting memory.

Consequently we would recommend the the relative accuracy requested is larger than machine epsilon by a factor of 100. Since machine epsilon depends on the size of the floating point type we provide a utility symbol MAXMOD_EPSILON which is the appropriate for the maxmod_float_t type.

If this advice is not followed then one can mitigate the effects of the explosion by setting the max.evaluations or max.intervals fields of the maxmod_opt_t structure.

We remark the this explosion phenomenon is rather dependant on the relative sizes of the maxmod_float_t and maxmod_int_t types, and this depends on the machine architecture. The 64-bit x86 architecture is affected but not the 32-bit.

AUTHOR

J. J. Green