Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “POLYNOMIALS”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 685 records · Page 38

Study on the mapping of dark matter clustering from real space to redshift space

The mapping of dark matter clustering from real space to redshift space introduces the anisotropic property to the measured density power spectrum in redshift space, known as the redshift space distortion effect. The mapping formula is intrinsically non-linear, which is complicated by the higher order polynomials due to indefinite cross correlations between the density and velocity fields, and the Finger-of-God effect due to the randomness of the peculiar velocity field. Whilst the full higher order polynomials remain unknown, the other systematics can be controlled consistently within the same order truncation in the expansion of the mapping formula, as shown in this paper. The systematic due to the unknown non-linear density and velocity fields is removed by separately measuring all terms in the expansion directly using simulations. The uncertainty caused by the velocity randomness is controlled by splitting the FoG term into two pieces, 1) the ''one-point' FoG term being independent of the separation vector between two different points, and 2) the ''correlated' FoG term appearing as an indefinite polynomials which is expanded in the same order as all other perturbative polynomials. Using 100 realizations of simulations, we find that the Gaussian FoG function with only one scale-independent free parameter works quite well, and that our new mapping formulation accurately reproduces the observed 2-dimensional density power spectrum in redshift space at the smallest scales by far, up to k ∼ 0.2 Mpc{sup -1}, considering the resolution of future experiments.

79 ASTRONOMY AND ASTROPHYSICS↗

Techniques to improve the accuracy of noise power spectrum measurements in digital x-ray imaging based on background trends removal

Purpose: Noise characterization through estimation of the noise power spectrum (NPS) is a central component of the evaluation of digital x-ray systems. Extensive works have been conducted to achieve accurate and precise measurement of NPS. One approach to improve the accuracy of the NPS measurement is to reduce the statistical variance of the NPS results by involving more data samples. However, this method is based on the assumption that the noise in a radiographic image is arising from stochastic processes. In the practical data, the artifactuals always superimpose on the stochastic noise as low-frequency background trends and prevent us from achieving accurate NPS. The purpose of this study was to investigate an appropriate background detrending technique to improve the accuracy of NPS estimation for digital x-ray systems. Methods: In order to achieve the optimal background detrending technique for NPS estimate, four methods for artifactuals removal were quantitatively studied and compared: (1) Subtraction of a low-pass-filtered version of the image, (2) subtraction of a 2-D first-order fit to the image, (3) subtraction of a 2-D second-order polynomial fit to the image, and (4) subtracting two uniform exposure images. In addition, background trend removal was separately applied within original region of interest or its partitioned sub-blocks for all four methods. The performance of background detrending techniques was compared according to the statistical variance of the NPS results and low-frequency systematic rise suppression. Results: Among four methods, subtraction of a 2-D second-order polynomial fit to the image was most effective in low-frequency systematic rise suppression and variances reduction for NPS estimate according to the authors' digital x-ray system. Subtraction of a low-pass-filtered version of the image led to NPS variance increment above low-frequency components because of the side lobe effects of frequency response of the boxcar filtering function. Subtracting two uniform exposure images obtained the worst result on the smoothness of NPS curve, although it was effective in low-frequency systematic rise suppression. Subtraction of a 2-D first-order fit to the image was also identified effective for background detrending, but it was worse than subtraction of a 2-D second-order polynomial fit to the image according to the authors' digital x-ray system. Conclusions: As a result of this study, the authors verified that it is necessary and feasible to get better NPS estimate by appropriate background trend removal. Subtraction of a 2-D second-order polynomial fit to the image was the most appropriate technique for background detrending without consideration of processing time.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Deterministic absorbed dose estimation in computed tomography using a discrete ordinates method

Purpose: Organ dose estimation for a patient undergoing computed tomography (CT) scanning is very important. Although Monte Carlo methods are considered gold-standard in patient dose estimation, the computation time required is formidable for routine clinical calculations. Here, the authors instigate a deterministic method for estimating an absorbed dose more efficiently. Methods: Compared with current Monte Carlo methods, a more efficient approach to estimating the absorbed dose is to solve the linear Boltzmann equation numerically. In this study, an axial CT scan was modeled with a software package, Denovo, which solved the linear Boltzmann equation using the discrete ordinates method. The CT scanning configuration included 16 x-ray source positions, beam collimators, flat filters, and bowtie filters. The phantom was the standard 32 cm CT dose index (CTDI) phantom. Four different Denovo simulations were performed with different simulation parameters, including the number of quadrature sets and the order of Legendre polynomial expansions. A Monte Carlo simulation was also performed for benchmarking the Denovo simulations. A quantitative comparison was made of the simulation results obtained by the Denovo and the Monte Carlo methods. Results: The difference in the simulation results of the discrete ordinates method and those of the Monte Carlo methods was found to be small, with a root-mean-square difference of around 2.4%. It was found that the discrete ordinates method, with a higher order of Legendre polynomial expansions, underestimated the absorbed dose near the center of the phantom (i.e., low dose region). Simulations of the quadrature set 8 and the first order of the Legendre polynomial expansions proved to be the most efficient computation method in the authors’ study. The single-thread computation time of the deterministic simulation of the quadrature set 8 and the first order of the Legendre polynomial expansions was 21 min on a personal computer. Conclusions: The simulation results showed that the deterministic method can be effectively used to estimate the absorbed dose in a CTDI phantom. The accuracy of the discrete ordinates method was close to that of a Monte Carlo simulation, and the primary benefit of the discrete ordinates method lies in its rapid computation speed. It is expected that further optimization of this method in routine clinical CT dose estimation will improve its accuracy and speed.

07 ISOTOPE AND RADIATION SOURCES↗

Calculation of Thermal Conductivity Coefficients of Electrons in Magnetized Dense Matter

The solution of Boltzmann equation for plasma in magnetic field with arbitrarily degenerate electrons and nondegenerate nuclei is obtained by Chapman−Enskog method. Functions generalizing Sonine polynomials are used for obtaining an approximate solution. Fully ionized plasma is considered. The tensor of the heat conductivity coefficients in nonquantized magnetic field is calculated. For nondegenerate and strongly degenerate plasma the asymptotic analytic formulas are obtained and compared with results of previous authors. The Lorentz approximation with neglecting of electron−electron encounters is asymptotically exact for strongly degenerate plasma. For the first time, analytical expressions for the heat conductivity tensor for nondegenerate electrons in the presence of a magnetic field are obtained in the three-polynomial approximation with account of electron−electron collisions. Account of the third polynomial improved substantially the precision of results. In the two-polynomial approximation, the obtained solution coincides with the published results. For strongly degenerate electrons, an asymptotically exact analytical solution for the heat conductivity tensor in the presence of a magnetic field is obtained for the first time. This solution has a considerably more complicated dependence on the magnetic field than those in previous publications and gives a several times smaller relative value of the thermal conductivity across the magnetic field at ωτ * 0.8.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Time and Frequency Domain Methods for Basis Selection in Random Linear Dynamical Systems

Polynomial chaos methods have been extensively used to analyze systems in uncertainty quantification. Furthermore, several approaches exist to determine a low-dimensional approximation (or sparse approximation) for some quantity of interest in a model, where just a few orthogonal basis polynomials are required. In this work, we consider linear dynamical systems consisting of ordinary differential equations with random variables. The aim of this paper is to explore methods for producing low-dimensional approximations of the quantity of interest further. We investigate two numerical techniques to compute a low-dimensional representation, which both fit the approximation to a set of samples in the time domain. On the one hand, a frequency domain analysis of a stochastic Galerkin system yields the selection of the basis polynomials. It follows a linear least squares problem. On the other hand, a sparse minimization yields the choice of the basis polynomials by information from the time domain only. An orthogonal matching pursuit produces an approximate solution of the minimization problem. Finally, we compare the two approaches using a test example from a mechanical application.

97 MATHEMATICS AND COMPUTING↗

Computational algebraic geometry for statistical modeling FY09Q2 progress.

This is a progress report on polynomial system solving for statistical modeling. This is a progress report on polynomial system solving for statistical modeling. This quarter we have developed our first model of shock response data and an algorithm for identifying the chamber cone containing a polynomial system in n variables with n+k terms within polynomial time - a significant improvement over previous algorithms, all having exponential worst-case complexity. We have implemented and verified the chamber cone algorithm for n+3 and are working to extend the implementation to handle arbitrary k. Later sections of this report explain chamber cones in more detail; the next section provides an overview of the project and how the current progress fits into it.

99 GENERAL AND MISCELLANEOUS↗

Topology of Large-scale Structures of Galaxies in Two Dimensions—Systematic Effects

We study the two-dimensional topology of galactic distribution when projected onto two-dimensional spherical shells. Using the latest Horizon Run 4 simulation data, we construct the genus of the two-dimensional field and consider how this statistic is affected by late-time nonlinear effects—principally gravitational collapse and redshift space distortion (RSD). We also consider systematic and numerical artifacts, such as shot noise, galaxy bias, and finite pixel effects. We model the systematics using a Hermite polynomial expansion and perform a comprehensive analysis of known effects on the two-dimensional genus, with a view toward using the statistic for cosmological parameter estimation. We find that the finite pixel effect is dominated by an amplitude drop and can be made less than 1% by adopting pixels smaller than 1/3 of the angular smoothing length. Nonlinear gravitational evolution introduces time-dependent coefficients of the zeroth, first, and second Hermite polynomials, but the genus amplitude changes by less than 1% between z = 1 and z = 0 for smoothing scales R{sub G}>9 Mpc/h. Non-zero terms are measured up to third order in the Hermite polynomial expansion when studying RSD. Differences in the shapes of the genus curves in real and redshift space are small when we adopt thick redshift shells, but the amplitude change remains a significant ∼O(10%) effect. The combined effects of galaxy biasing and shot noise produce systematic effects up to the second Hermite polynomial. It is shown that, when sampling, the use of galaxy mass cuts significantly reduces the effect of shot noise relative to random sampling.

79 ASTRONOMY AND ASTROPHYSICS↗

Sensitivity Analysis of Passive Heat Removal Capability of FHR Based on Efficient Surrogate Model and GenFlow

Code Scaling, Applicability and Uncertainty Evaluation Methodology (CSAU) is used for quantifying reactor safety margins and works as an alternative method for licensing nuclear power plant. In the framework of CSAU, sensitivity and uncertainty analysis (SA and UA) should be performed. However, for large-scale complicated thermal hydraulics analysis simulated by code (e.g. RELAP5, CFD and subchannel analysis, the sensitivity and uncertainty analysis is really time-consuming. Furthermore, sometimes it is not feasible to perform SA and UA. Specifically, the computation time for Monte Carlo sampling or advanced LHS sampling can be neglected, but the computation time for thermal hydraulics code makes up main part of time during SA and UA process. In order to accelerate the speed of SA and UA, thermal hydraulics code can be improved based on advanced mathematic algorithm or using parallel method. However, the development for new mathematic method needs long time and strict verification and validation process is needed for a new code, which usually takes a couple of years or even longer time to have an approved code that can be used in nuclear industry. An alternative way to improve the speed of SA and UA is using surrogate model. The surrogate model is derived from the input as well as output data of the original code, assuming the code as a black box. The most common method is using response surface method (RSM) as a surrogate for the code, the input parameters are then sampled from their assumed distribution and the corresponding value of the response surface function is calculated. However, a couple of input parameters need hundreds or even thousands of original code calculations. The large number of runs is an obvious disadvantage of this method. Besides, the second disadvantage is an appropriate response surface function must be selected (e.g. quadratic, cubic, quartic, with or without cross product terms, or using a non-polynomial form) to avoid the overfit and underfit problem. This process is time consuming and expensive. Polynomial chaos expansion method is a reasonably fast and attractive alternative, stochastic model. The chaos expansion provides an efficient high-order method of including non-linear effects in stochastic analysis. Usually, the information about the model parameters and their probability distribution is limited and the dependence between them is not known. However, if arbitrary polynomial chaos is used, instead of assuming probability distribution for input parameters which may introduces additional subjectivity into the analysis, the available information can directly and most purely be used in stochastic analysis based on arbitrary data distribution. Thus, it is not necessary to know the exact probability density functions to perform SA and UA based on arbitrary polynomial chaos (aPC). The aPC has been applied for uncertainty quantification in many fields (e.g. in solid mechanics, fluid flows, thermal sciences), and become widely used in nuclear industry recently. Mk1 PB-FHR is a small modular fluoride-salt-cooled, high-temperature reactors (FHRs) that is a concept design by University of California, Berkeley (UCB). It has inherently safe features like natural-circulation-driven systems (e.g. direct reactor auxiliary cooling system (DRACS)) to passively remove decay heat from the reactor core during design basis and beyond design. It is necessary to perform SA and UA, since the licensing process of this new kind of reactor is under way and there are many design parameters that have not been fixed. Current nuclear commercial codes, such as RELAP5, have mainly been developed for light water reactors, which require the use of comprehensive two-phase flow models. This capability is not required to simulate single-phase flow phenomena in FHRs, whose baseline coolant, flibe, remains liquid up to 1430 deg. C at atmospheric pressure. The FHR advanced natural circulation analysis (FANCY) code has been developed specifically for FHR technology modeling and validation work has been performed by using CIET data in UCB. The code has been renamed General Flow (GenFlow) because it has been further developed to have the capability to model complicated pipework system based on object-oriented concept for user friendly purpose. Besides, it can be used to simulate both the force circulation as well as natural circulation. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

A Parallel Reconstructed Discontinuous Galerkin Method for the Compressible Flows on Aritrary Grids

A reconstruction-based discontinuous Galerkin method is presented for the solution of the compressible Navier-Stokes equations on arbitrary grids. In this method, an in-cell reconstruction is used to obtain a higher-order polynomial representation of the underlying discontinuous Galerkin polynomial solution and an inter-cell reconstruction is used to obtain a continuous polynomial solution on the union of two neighboring, interface-sharing cells. The in-cell reconstruction is designed to enhance the accuracy of the discontinuous Galerkin method by increasing the order of the underlying polynomial solution. The inter-cell reconstruction is devised to remove an interface discontinuity of the solution and its derivatives and thus to provide a simple, accurate, consistent, and robust approximation to the viscous and heat fluxes in the Navier-Stokes equations. A parallel strategy is also devised for the resulting reconstruction discontinuous Galerkin method, which is based on domain partitioning and Single Program Multiple Data (SPMD) parallel programming model. The RDG method is used to compute a variety of compressible flow problems on arbitrary meshes to demonstrate its accuracy, efficiency, robustness, and versatility. The numerical results demonstrate that this RDG method is third-order accurate at a cost slightly higher than its underlying second-order DG method, at the same time providing a better performance than the third order DG method, in terms of both computing costs and storage requirements.

97 MATHEMATICS AND COMPUTING↗

Extended kinetic lattice grand canonical Monte Carlo simulation method for transport of multicomponent ion mixtures through a model nanopore system

Abstract An extended version of the original kinetic lattice grand canonical Monte Carlo simulation method combined with mean field theory (KLGCMC/MF) ( J. Chem. Phys. 2007 , 127, 024706) is presented for the study of transport of multicomponent ion mixtures through a model nanopore. Comparison of the extended KLGCMC/MF (eKLGCMC/MF) simulation results with Poisson–Nernst–Planck (PNP) calculations is also made to confirm the validity of the extended simulation approach. Unlike the original version of KLGCMC/MF simulation method that treats only a binary ionic solution with one cation and one anion species, this extended version can deal with a system that includes ternary ion mixtures. A diffusion probability algorithm is also added to the extended version of the simulation method to describe the inhomogeneous diffusivity of ions that is often observed in the ion permeation through nanopores. Both Legendre and Chebyshev polynomials of the second kind were tested as a basis set for the basis set expansion (BSE) method with which to calculate the reaction field energy in the eKLGCMC/MF simulation. It turned out that the Legendre polynomials perform better than the Chebyshev polynomials, and as a result, the Legendre polynomials were implemented in the current version of eKLGCMC/MF simulation algorithm. The presented eKLGCMC/MF simulation method with new features finds its potential applications in nanopore systems where the correlation between ion species with the same sign of charges plays a key role such as oscillating ion currents or anomalous mole fraction effects.

Choi, Inhyeok↗

FELIX-2.0: New version of the finite element solver for the time dependent generator coordinate method with the Gaussian overlap approximation

The time-dependent generator coordinate method (TDGCM) is a powerful method to study the largeamplitude collective motion of quantum many-body systems such as atomic nuclei. Under the GaussianOverlap Approximation (GOA), the TDGCM leads to a local, time-dependent Schrödinger equation in amulti-dimensional collective space. In this paper, we present the version 2.0 of the code FELIX that solvesthe collective Schrödinger equation in a finite element basis. This new version features: (i) the ability tosolve a generalized TDGCM+GOA equation with a metric term in the collective Hamiltonian, (ii) supportfor new kinds of finite elements and different types of quadrature to compute the discretized Hamiltonianand overlap matrices, (iii) the possibility to leverage the spectral element scheme, (iv) an explicit Krylovapproximation of the time propagator for time integration instead of the implicit Crank–Nicolson methodimplemented in the first version, (v) an entirely redesigned workflow. We benchmark this release on ananalytic problem as well as on realistic two-dimensional calculations of the low-energy fission of240Puand256Fm. Low to moderate numerical precision calculations are most efficiently performed with simplexelements with a degree 2 polynomial basis. Higher precision calculations should instead use the spectralelement method with a degree 4 polynomial basis. We emphasize that in a realistic calculation of fissionmass distributions of240Pu, FELIX-2.0 is about 20 times faster than its previous release (within a numericalprecision of a few percents).

Regnier, D.↗

Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods

In this study, we develop a new tensor-product based preconditioner for discontinuous Galerkin methods with polynomial degrees higher than those typically employed. This preconditioner uses an automatic, purely algebraic method to approximate the exact block Jacobi preconditioner by Kronecker products of several small, one-dimensional matrices. Traditional matrix-based preconditioners require O ( p 2d ) storage and O ( p 3d ) computational work, where p is the degree of basis polynomials used, and d is the spatial dimension. Our SVD-based tensor-product preconditioner requires O ( p d+1 ) storage, O ( p d+1 ) work in two spatial dimensions, and O ( p d+2 ) work in three spatial dimensions. Combined with a matrix-free Newton–Krylov solver, these preconditioners allow for the solution of DG systems in linear time in p per degree of freedom in 2D, and reduce the computational complexity from O ( p 9 ) to O ( p 5 ) in 3D. Numerical results are shown in 2D and 3D for the advection, Euler, and Navier–Stokes equations, using polynomials of degree up to p = 30. For many test cases, the preconditioner results in similar iteration counts when compared with the exact block Jacobi preconditioner, and performance is significantly improved for high polynomial degrees p .

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Adaptive spectral solution method for the Landau and Lenard-Balescu equations

In this paper, we present an adaptive spectral method for solving the Landau/Fokker-Planck equation for electron-ion systems. The heart of the algorithm is an expansion in Laguerre polynomials, which has several advantages, including automatic conservation of both energy and particles without the need for any special discretization or time-stepping schemes. One drawback of such an expansion is the O(N 3 ) memory requirement, where N is the number of polynomials used. This can impose an inconvenient limit in cases of practical interest, such as when two particle species have widely separated temperatures. The algorithm we describe here addresses this problem by periodically re-projecting the solution onto a judicious choice of new basis functions that are still Laguerre polynomials but have arguments adapted to the current physical conditions. This results in a reduction in the number of polynomials needed, at the expense of increased solution time. Because the equations are solved with little difficulty, this added time is not of much concern compared to the savings in memory. To demonstrate the algorithm, we solve several relaxation problems that could not be computed with the spectral method without re-projection. Another major advantage of this method is that it can be used for collision operators more complicated than that of the Landau equation, and we demonstrate this here by using it to solve the non-degenerate quantum Lenard-Balescu (QLB) equation for a hydrogen plasma. We conclude with some comparisons of temperature relaxation problems solved with the latter equation and the Landau equation with a Coulomb logarithm inspired by the properties of the QLB operator. We find that with this choice of Coulomb logarithm, there is little difference between using the two equations for these particular systems.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

A method for bounding high-order finite element functions: Applications to mesh validity and bounds-preserving limiters

We introduce a novel method for bounding high-order multi-dimensional polynomials in finite element approximations. The method involves precomputing optimal piecewise-linear bounding boxes for polynomial basis functions, which can then be used to locally bound any combination of these basis functions. This approach can be applied to any element/basis type at any approximation order, can provide local (i.e., subcell) extremum bounds to a desired level of accuracy, and can be evaluated efficiently on-the-fly in simulations. Furthermore, we show that this approach generally yields more accurate bounds in comparison to traditional methods based on convex hull properties (e.g., Bernstein polynomials). Furthermore, the efficacy of this technique is shown in applications such as mesh validity checks and optimization for high-order curved meshes, where positivity of the element Jacobian determinant can be ensured throughout the entire element, and continuously bounds-preserving limiters for hyperbolic systems, which can enforce maximum principle bounds across the entire solution polynomial.

Bounding box↗

Measurement of EUV lithography pupil amplitude and phase variation via image-based methodology

Here, an approach to image-based EUV aberration metrology using binary mask targets and iterative model-based solutions to extract both the amplitude and phase components of the aberrated pupil function is presented. The approach is enabled through previously developed modeling, fitting, and extraction algorithms. We seek to examine the behavior of pupil amplitude variation in real-optical systems. Optimized target images were captured under several conditions to fit the resulting pupil responses. Both the amplitude and phase components of the pupil function were extracted from a zone-plate-based EUV mask microscope. The pupil amplitude variation was expanded in three different bases: Zernike polynomials, Legendre polynomials, and Hermite polynomials. It was found that the Zernike polynomials describe pupil amplitude variation most effectively of the three.

60 APPLIED LIFE SCIENCES↗

Decayheatml

This code is designed to predict and analyze the decay heat generated in molten salt reactors (MSRs) using a hybrid approach that combines machine learning and segmented polynomial fitting. The accurate prediction of decay heat is essential for reactor safety and the optimization of spent fuel storage. The code operates through several key components: 1) Data Architecture: It incorporates a modular data architecture that handles various MSR-specific operational parameters such as power density, humidity content, and air ingress. These parameters are sampled using Sobol sequences to ensure comprehensive coverage of operational uncertainties. 2) Machine Learning Framework: The code employs a diverse set of machine learning models, including polynomial regression, decision trees, random forests, gradient boosting, support vector regression, k-nearest neighbors, multi-layer perceptrons, and symbolic regression. These models are trained to predict decay heat over a wide temporal range, from immediate shutdown up to 10,000 years. 3) Region-Optimized Training: The temporal domain is divided into multiple regions, each modeled separately to capture distinct decay heat characteristics across different time scales. This approach significantly improves the accuracy and interpretability of predictions. 4) Segmented Polynomial Interpretation (SPI): The SPI method translates machine learning predictions into piecewise polynomial equations. These equations are physically interpretable and can be directly integrated into existing engineering workflows and safety analyses. 5) Front-End Interfaces: The code includes both a Jupyter notebook interface for research development and a Streamlit web application for operational deployment. These interfaces allow users to interactively explore decay heat predictions, adjust operational parameters, and visualize results in real-time. 6) Applications: The framework supports various applications, including safety system validation and spent fuel container optimization. It enables real-time evaluation of worst-case decay heat scenarios, informing the design of passive safety systems and optimizing container designs for long-term storage. Overall, this code provides a robust, accurate, and user-friendly tool for predicting decay heat in MSRs, enhancing reactor safety, and optimizing spent fuel management.

Retamales, Mauricio Eduardo Tano [Idaho National L↗

Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics

The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero–nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime.

97 MATHEMATICS AND COMPUTING↗

A contracting-interval program for the Danilewski method

The concept of contracting-interval programs is applied to finding the eigenvalues of a matrix. The development is a three-step process in which (1) a program is developed for the reduction of a matrix to Hessenberg form, (2) a program is developed for the reduction of a Hessenberg matrix to colleague form, and (3) the characteristic polynomial with interval coefficients is readily obtained from the interval of colleague matrices. This interval polynomial is then factored into quadratic factors so that the eigenvalues may be obtained. To develop a contracting-interval program for factoring this polynomial with interval coefficients it is necessary to have an iteration method which converges even in the presence of controlled rounding errors. A theorem is stated giving sufficient conditions for the convergence of Newton's method when both the function and its Jacobian cannot be evaluated exactly but errors can be made proportional to the square of the norm of the difference between the previous two iterates. This theorem is applied to prove the convergence of the generalization of the Newton-Bairstow method that is used to obtain quadratic factors of the characteristic polynomial.

Harris, J. D.↗