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#
Below, the symbol T refers to a parametric real type that may be Float32
(single precision) or Float64 (double precision).
Calable functions as described are with T as Float64, but variants
(with the additional suffix _s
, e.g., roots_initialize_s
)
are available with T as Float32.
callable functions#
function roots_initialize(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 Int32 that gives the exit status from the package. Possible values are (currently):
|
function roots_information(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 Int32 that gives the exit status from the package. Possible values are (currently):
|
function roots_terminate(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} f_indexing::Bool error::Int32 out::Int32 print_level::Int32 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
Int32 error
error and warning diagnostics occur on stream error
Int32 out
general output occurs on stream out
Int32 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 status::Int32 alloc_status::Int32 bad_alloc::NTuple{81,Cchar}
detailed documentation#
inform derived type as a Julia structure
components#
Int32 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.
Int32 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