A classical mathematical proof is constructed using pencil and paper. However, there are many ways in which computers may be used in a mathematical proof. But ‘proof by computer’, or even the use of ...computers in the course of a proof, is not so readily accepted (the December 2008 issue of the Notices of the American Mathematical Society is devoted to formal proofs by computer). In the following we introduce verification methods and discuss how they can assist in achieving a mathematically rigorous result. In particular we emphasize how floating-point arithmetic is used.
The numerical computation of the Euclidean norm of a vector is perfectly well conditioned with favorite a priori error estimates. Recently there is interest in computing a faithfully rounded ...approximation which means that there is no other floating-point number between the computed and the true real result. Hence the result is either the rounded to nearest result or its neighbor. Previous publications guarantee a faithfully rounded result for large dimension, but not the rounded to nearest result. In this note we present several new and fast algorithms producing a faithfully rounded result, as well as the first algorithm to compute the rounded to nearest result. Executable MATLAB codes are included. As a by product, a fast loop-free error-free vector transformation is given. That transforms a vector such that the sum remains unchanged but the condition number of the sum multiplies with the rounding error unit.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Summary Background Imaging with amyloid-β PET can potentially aid the early and accurate diagnosis of Alzheimer's disease. Florbetaben (18 F) is a promising18 F-labelled amyloid-β-targeted PET tracer ...in clinical development. We aimed to assess the sensitivity and specificity of florbetaben (18 F) PET in discriminating between patients with probable Alzheimer's disease and elderly healthy controls. Methods We did a multicentre, open-label, non-randomised phase 2 study in 18 centres in Australia, Germany, Switzerland, and the USA. Imaging with florbetaben (18 F) PET was done on patients with probable Alzheimer's disease (age 55 years or older, mini-mental state examination MMSE score=18–26, clinical dementia rating CDR=0·5–2·0) and age-matched healthy controls (MMSE ≥28, CDR=0). Our primary objective was to establish the diagnostic efficacy of the scans in differentiating between patients with probable disease and age-matched healthy controls on the basis of neocortical tracer uptake pattern 90–110 min post-injection. PET images were assessed visually by three readers masked to the clinical diagnosis and all other clinical findings, and quantitatively by use of pre-established brain volumes of interest to obtain standard uptake value ratios (SUVRs), taking the cerebellar cortex as the reference region. This study is registered with ClinicalTrials.gov , number NCT00750282. Findings 81 participants with probable Alzheimer's disease and 69 healthy controls were assessed. Independent visual assessment of the PET scans showed a sensitivity of 80% (95% CI 71–89) and a specificity of 91% (84–98) for discriminating participants with Alzheimer's disease from healthy controls. The SUVRs in all neocortical grey-matter regions in participants with Alzheimer's disease were significantly higher (p<0·0001) compared with the healthy controls, with the posterior cingulate being the best discriminator. Linear discriminant analysis of regional SUVRs yielded a sensitivity of 85% and a specificity of 91%. Regional SUVRs also correlated well with scores of cognitive impairment such as the MMSE and the word-list memory and word-list recall scores ( r −0·27 to −0·33, p≤0·021). APOE ε4 was more common in participants with positive PET images compared with those with negative scans (65% vs 22% p=0·027 in patients with Alzheimer's disease; 50% vs 16% p=0·074 in healthy controls). No safety concerns were noted. Interpretation We provide verification of the efficacy, safety, and biological relevance of florbetaben (18 F) amyloid-β PET and suggest its potential as a visual adjunct in the diagnostic algorithm of dementia. Funding Bayer Schering Pharma AG.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
Recently Oishi published a paper allowing lower bounds for the minimum singular value of coefficient matrices of linearized Galerkin equations, which in turn arise in the computation of periodic ...solutions of nonlinear delay differential equations with some smooth nonlinearity. The coefficient matrix of linearized Galerkin equations may be large, so the computation of a valid lower bound of the smallest singular value may be costly. Oishi’s method is based on the inverse of a small upper left principal submatrix, and subsequent computations use a Schur complement with small computational cost. In this note some assumptions are removed and the bounds improved. Furthermore a technique is derived to reduce the total computationally cost significantly allowing to treat infinite dimensional matrices.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
This paper gives details on how to obtain mathematically rigorous results for global unconstrained and equality constrained optimization problems, as well as for finding all roots of a nonlinear ...function within a box. When trying to produce mathematically rigorous results for such problems of global nature, the main issue is to mathematically verify that a certain sub-box cannot contain a solution to the problem, i.e. to discard boxes. The presented verification methods are based on mathematical theorems, the assumptions of which are verified using Algorithmic Differentiation and interval arithmetic. In contrast to traditional numerical algorithms, the main problem of verification methods is how to formulate those assumptions. We present mathematical and implementation details on how to obtain fast verification algorithms in pure Matlab/Octave code. The methods are implemented in INTLAB, the Matlab/Octave toolbox for Reliable Computing. Several examples together with executable code show advantages and weaknesses of the proposed methods. New results are included, however, the main goal is to introduce and give enough details to understand black-box Matlab/Octave routines to solve the mentioned problems. An outlook on current research on verification methods for large problems with several million variables and several tens of thousands of constraints based on conic programming is given as well. The latter can be regarded as an extension of interval arithmetic.
Full text
Available for:
BFBNIB, DOBA, GIS, IJS, IZUM, KILJ, KISLJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
7.
Learned Fitting of Spatially Varying BRDFs Merzbach, S.; Hermann, M.; Rump, M. ...
Computer graphics forum,
July 2019, 2019-07-00, 20190701, Volume:
38, Issue:
4
Journal Article
Peer reviewed
The use of spatially varying reflectance models (SVBRDF) is the state of the art in physically based rendering and the ultimate goal is to acquire them from real world samples. Recently several ...promising deep learning approaches have emerged that create such models from a few uncalibrated photos, after being trained on synthetic SVBRDF datasets. While the achieved results are already very impressive, the reconstruction accuracy that is achieved by these approaches is still far from that of specialized devices. On the other hand, fitting SVBRDF parameter maps to the gibabytes of calibrated HDR images per material acquired by state of the art high quality material scanners takes on the order of several hours for realistic spatial resolutions. In this paper, we present a first deep learning approach that is capable of producing SVBRDF parameter maps more than two orders of magnitude faster than state of the art approaches, while still providing results of equal quality and generalizing to new materials unseen during the training. This is made possible by training our network on a large‐scale database of material scans that we have gathered with a commercially available SVBRDF scanner. In particular, we train a convolutional neural network to map calibrated input images to the 13 parameter maps of an anisotropic Ward BRDF, modified to account for Fresnel reflections, and evaluate the results by comparing the measured images against re‐renderings from our SVBRDF predictions. The novel approach is extensively validated on real world data taken from our material database, which we make publicly available under https://cg.cs.uni‐bonn.de/svbrdfs/.
Full text
Available for:
BFBNIB, DOBA, FZAB, GIS, IJS, IZUM, KILJ, NLZOH, NUK, OILJ, PILJ, PNG, SAZU, SBCE, SBMB, UILJ, UKNU, UL, UM, UPUK
Given a vector of floating-point numbers with exact sum $s$, we present an algorithm for calculating a faithful rounding of $s$, i.e., the result is one of the immediate floating-point neighbors of ...$s$. If the sum $s$ is a floating-point number, we prove that this is the result of our algorithm. The algorithm adapts to the condition number of the sum, i.e., it is fast for mildly conditioned sums with slowly increasing computing time proportional to the logarithm of the condition number. All statements are also true in the presence of underflow. The algorithm does not depend on the exponent range. Our algorithm is fast in terms of measured computing time because it allows good instruction-level parallelism, it neither requires special operations such as access to mantissa or exponent, it contains no branch in the inner loop, nor does it require some extra precision: The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain constants used in the algorithm are proved to be optimal.
Full text
Available for:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
We present a pair arithmetic for the four basic operations and square root. It can be regarded as a simplified, more-efficient double-double arithmetic. The central assumption on the underlying ...arithmetic is the first standard model for error analysis for operations on a discrete set of real numbers. Neither do we require a floating-point grid nor a rounding to nearest property. Based on that, we define a relative rounding error unit u and prove rigorous error bounds for the computed result of an arbitrary arithmetic expression depending on u, the size of the expression, and possibly a condition measure. In the second part of this note, we extend the error analysis by examining requirements to ensure faithfully rounded outputs and apply our results to IEEE 754 standard conform floating-point systems. For a class of mathematical expressions, using an IEEE 754 standard conform arithmetic with base β, the result is proved to be faithfully rounded for up to 1 / √βu - 2 operations. Our findings cover a number of previously published algorithms to compute faithfully rounded results, among them Horner’s scheme, products, sums, dot products, or Euclidean norm. Beyond that, several other problems can be analyzed, such as polynomial interpolation, orientation problems, Householder transformations, or the smallest singular value of Hilbert matrices of large size.
In recent years, considerable effort in the field of operations research has been paid to optimizing airline operations, including the logistics of an airline’s fleet of aircraft. We focus on the ...problem of aircraft routing, which involves generating and selecting a particular route for each aircraft of a sub-fleet that is already assigned to a set of feasible sequences of flight legs. Similar studies typically focus on long-term route planning. However, stochastic events such as severe weather changes, equipment failures, variable maintenance times, or even new regulations mandated by the Federal Aviation Administration (FAA) play havoc on these long-term plans. In addition, these long-term plans ignore detailed maintenance requirements by considering only one or two of the primary maintenance checks that must be performed on a regular, long-term basis. As a result, these plans are often ignored by personnel in airline operations who are forced on a daily basis to develop quick, ad hoc methods to address these maintenance requirements and other irregular events. To address this problem, we develop an operational aircraft maintenance routing problem formulation that includes maintenance resource availability constraints. We propose a branch-and-price algorithm for solving this problem, which, due to the resource constraints, entails a modification of the branch-on, follow-on branching rule typically used for solving similar problems. Through computational testing, we explore the efficiency of this solution approach under a combination of heuristic choices for column (route) generation and selection.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK