GALAHAD ROOTS package#

purpose#

The roots package uses classical formulae together with Newton’s method to find all the real roots of a real polynomial.

Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!

See Section 4 of $GALAHAD/doc/roots.pdf for additional details.

method#

Littlewood and Ferrari’s algorithms are used to find estimates of the real roots of cubic and quartic polynomials, respectively; a stabilized version of the well-known formula is used in the quadratic case. Newton’s method and/or methods based on the companion matrix are used to further refine the computed roots if necessary. Madsen and Reid’s (1975) method is used for polynomials whose degree exceeds four.

reference#

The basic method is that given by

K. Madsen and J. K. Reid, ``FORTRAN Subroutines for Finding Polynomial Zeros’’. Technical Report A.E.R.E. R.7986, Computer Science and System Division, A.E.R.E. Harwell, Oxfordshire (1975)

parametric real type T and integer type INT#

Below, the symbol T refers to a parametric real type that may be Float32 (single precision), Float64 (double precision) or, if supported, Float128 (quadruple precision). The symbol INT refers to a parametric integer type that may be Int32 (32-bit integer) or Int64 (64-bit integer).

callable functions#

    function roots_initialize(T, INT, data, control, status)

Set default control values and initialize private data

Parameters:

data

holds private internal data

control

is a structure containing control information (see roots_control_type)

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are (currently):

0
The initialization was successful.

    function roots_information(T, INT, data, inform, status)

Provides output information

Parameters:

data

holds private internal data

inform

is a structure containing output information (see roots_inform_type)

status

is a scalar variable of type INT that gives the exit status from the package. Possible values are (currently):

0
The values were recorded successfully

    function roots_terminate(T, INT, data, control, inform)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a structure containing control information (see roots_control_type)
inform	is a structure containing output information (see roots_inform_type)

available structures#

roots_control_type structure#

    struct roots_control_type{T,INT}
      f_indexing::Bool
      error::INT
      out::INT
      print_level::INT
      tol::T
      zero_coef::T
      zero_f::T
      space_critical::Bool
      deallocate_error_fatal::Bool
      prefix::NTuple{31,Cchar}

detailed documentation#

control derived type as a Julia structure

components#

Bool f_indexing

use C or Fortran sparse matrix indexing

INT error

error and warning diagnostics occur on stream error

INT out

general output occurs on stream out

INT print_level

the level of output required is specified by print_level

T tol

the required accuracy of the roots

T zero_coef

any coefficient smaller in absolute value than zero_coef will be regarde to be zero

T zero_f

any value of the polynomial smaller in absolute value than zero_f will be regarded as giving a root

Bool space_critical

if .space_critical true, every effort will be made to use as little space as possible. This may result in longer computation time

Bool deallocate_error_fatal

if .deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue

NTuple{31,Cchar} prefix

all output lines will be prefixed by .prefix(2:LEN(TRIM(.prefix))-1) where .prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

roots_inform_type structure#

    struct roots_inform_type{INT}
      status::INT
      alloc_status::INT
      bad_alloc::NTuple{81,Cchar}

detailed documentation#

inform derived type as a Julia structure

components#

INT status

return status. Possible values are:

0

The call was successful.
-1

An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-2

A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-3

Either the specified degree of the polynomial in degree is less than 0, or the declared dimension of the array roots is smaller than the specified degree.

INT alloc_status

the status of the last attempted allocation/deallocation

NTuple{81,Cchar} bad_alloc

the name of the array for which an allocation/deallocation error occurred

Index