The Complex Process of Converting Tools into Mathematical Instruments: The Case of Calculators

Transforming any tool into a mathematical instrument for students involves a complex ‘instrumentation’ process and does not necessarily lead to better mathematical understanding. Analysis of the constraints and potential of the artefact are necessary in order to point out the mathematical knowledge involved in using a calculator. Results of this analysis have an influence on the design of problem situations. Observations of students using graphic and symbolic calculators were analysed and categorised into profiles, illustrating that transforming the calculator into an efficient mathematical instrument varies from student to student, a factor which has to be included in the teaching process. This revised version was published online in August 2006 with corrections to the Cover Date.     

Symbolic computation of limit cycles associated with Hilbert’s 16th problem

This paper is concerned with the practical complexity of the symbolic computation of limit cycles associated with Hilbert’s 16th problem. In particular, in determining the number of small-amplitude limit cycles of a non-linear dynamical system, one often faces computing the focus values of Hopf-type critical points and solving lengthy coupled polynomial equations. These computations must be carried out through symbolic computation with the aid of a computer algebra system such as Maple or Mathematica, and thus usually gives rise to very large algebraic expressions. In this paper, efficient computations for the focus values and polynomial equations are discussed, showing how to deal with the complexity in the computation of non-linear dynamical systems.     

Interacting with local and remote data repositories using the stashR package

The stashR package (a Set of Tools for Administering Shared Repositories) for R implements a basic versioned key-value style database where character string keys are associated with data values. Using the S4 classes ‘localDB’ and ‘remoteDB’, and associated methods, versioned key-value databases can be either created locally on the user’s computer or accessed remotely via the Internet. The stashR package can enhance reproducible research by providing a ‘localDB’ database format for the caching of computations which can subsequently be stored on the Internet. To reproduce a particular computation, a reader can access the ‘remoteDB’ database and obtain the associated R objects. This work was supported in part by the Johns Hopkins Training Program in the Epidemiology and Biostatistics of Aging (NIA T32 AG00247) and the Faculty Innovation Fund, Johns Hopkins Bloomberg School of Public Health.     

Heuristic optimisation in financial modelling

There is a large number of optimisation problems in theoretical and applied finance that are difficult to solve as they exhibit multiple local optima or are not ‘well-behaved’ in other ways (e.g., discontinuities in the objective function). One way to deal with such problems is to adjust and to simplify them, for instance by dropping constraints, until they can be solved with standard numerical methods. We argue that an alternative approach is the application of optimisation heuristics like Simulated Annealing or Genetic Algorithms. These methods have been shown to be capable of handling non-convex optimisation problems with all kinds of constraints. To motivate the use of such techniques in finance, we present several actual problems where classical methods fail. Next, several well-known heuristic techniques that may be deployed in such cases are described. Since such presentations are quite general, we then describe in some detail how a particular problem, portfolio selection, can be tackled by a particular heuristic method, Threshold Accepting. Finally, the stochastics of the solutions obtained from heuristics are discussed. We show, again for the example from portfolio selection, how this random character of the solutions can be exploited to inform the distribution of computations.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

A probabilistic framework for the design of instance-based supervised ranking algorithms in an ordinal setting

In this article, we present a probabilistic framework which serves as the base from which instance-based algorithms for solving the supervised ranking problem may be derived. This framework constitutes a simple and novel approach to the supervised ranking problem, and we give a number of typical examples of how this derivation can be achieved. In this general framework, we pursue a cumulative and stochastic approach, relying heavily upon the concept of stochastic dominance. We show how the median can be used to extract, in a consistent way, a single (classification) label from a returned cumulative probability distribution function. We emphasize that all operations used are mathematically sound, i.e. they only make use of ordinal properties. Mostly, when confronted with the problem of learning a ranking, the training data is not monotone in itself, and some cleansing operation is performed on it to remove these ‘inconsistent’ examples. Our framework, however, deals with these occurrences of ‘reversed preference’ in a non-invasive way. On the contrary, it even allows to incorporate information gained from the occurrence of these reversed preferences. This is exactly what happens in the second realization of the main theorem.     

Fast computation of the field of a vertical magnetic dipole above a layered medium

We consider the direct problem of aeroelectrosounding for a layered medium. The specific feature of this problem is that its solution is representable as a Bessel transform of a function ƒ of a certain type. We have developed and implemented a method for fast computation of the Bessel transform of such functions. The method relies on the approximation of ƒ by a linear combination of exponentials with prespecified exponents. The Bessel transform of the original function ƒ is computed analytically as the Bessel transform of the approximating linear combination. Numerical computations have been carried out. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 39–48, 2007.     

Mental Computation of Students in a Reform-Based Mathematics Curriculum

Traditional school instruction in mathematics has generally produced students who are poor at mental computation and exhibit a weak sense of number and mathematical operations. In this study, fifth graders who had been in a reform-based mathematics curriculum since kindergarten were given a whole-class test on mental computation problems. Baseline data with students in traditional mathematics curricula were used as a comparison. The students in this reform-based mathematics curriculum performed much higher than the comparison group on all but one problem, and on most problems, this difference was substantial. Additionally, a student preference survey indicated that students in the reform curriculum were more likely to consider the calculator as an option than were the baseline group. They were also more able to recognize problems that did not lend themselves to mental computation. Individual interviews indicated that experiences in the primary grades with “invented” algorithms and discussing alternative solutions led to a better ability to compute mentally and a stronger number sense.     

Acquiring new use of multiplication through classroom teaching: an exploratory study

This article analyzes the process in which pupils acquire new uses of multiplication to measure area. Behaviors of five 4th-grade pupils in a series of lessons on areas were studied in depth by qualitative case-study methodology. Their use of multiplication changed as the lesson evolved, characterized conceptually as “using multiplication as a label,” “using it positively to approach problems which have not been solved before,” and “using it effectively to achieve the goal of measuring areas.” These three phases show the pupils’ understanding of multiplication in the context of measuring areas from a secondary accompaniment to a powerful tool of thinking. The phases observed and the students’ progress between the phases differs noticeably among the pupils. Factors that foster learners’ progress are investigated by comparing their behaviors.     

A simple heuristic for the multi item single level capacitated lotsizing problem

This paper presents a fast and flexible heuristic for the multi item capacitated lotsizing problem. The lotsizing step requires only O(NT) computations which is at least an order of magnitude faster than other well-known heuristics. The method is flexible since it allows the user to specify features such as how to sort items, which criterion to use in combining lots and how to search the demand matrix. Extensive computational results show that the new method outperforms existing heuristics both in terms of average solution quality and required computation times.     

A fast heuristic for a three-dimensional non-convex domain loading problem

In this paper we tackle a three-dimensional non-convex domain loading problem. We have to efficiently load identical small boxes into a highly irregular non-convex domain. The boxes to be loaded have a particular shape. If d is the length of the smallest edge of the box, its dimensions are d × nd × md, n ≤ m, with n and m integer values. This loading problem arises from an industrial design problem where it is necessary to obtain good solutions with very low computation time. We propose a fast heuristic based on an approximate representation of the non-convex domain in terms of cubes of dimension d and on the decomposition of the whole problem in several two-dimensional subproblems related to ‘planes’ of height d. The proposed heuristic shows good performances in terms of quality of solution and computation times. The results on several real test cases, coming from the industrial application, are shown.     

Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem

We study a scheduling problem motivated by the challenges observed in the newest semiconductor manufacturing wafer fabrication facilities. As wafers are larger and heavier in these wafer fabs, it is becoming more common to use specialized material handling containers that carry multiple orders coming from different customers and to schedule the containers as jobs in the fab. The system performance is a function of the completion times of orders, which ultimately depend on both (1) how the orders are assigned to such containers (“job formation”), and (2) how the containers are scheduled in the fab (“job scheduling”). The overall problem is to find the best way to form and schedule the jobs subject to complicating constraints, including the restrictions on the number of containers that can be used at one time and on the number of wafers the containers can carry. We focus on the single machine job formation and scheduling problem with the total completion time objective. We show that this problem is quite different from conventional parallel and serial batching scenarios and prove that the uncapacitated special case is polynomially solvable and the capacitated case is strongly NP-hard. We use a dynamic programming algorithm to solve the uncapacitated problem, which not only provides tight lower bounds for the capacitated problem, but also becomes a basis for a heuristic approach for the capacitated problem. The computational results show that this approach is very effective, leading to small optimality gaps that get even smaller as the problems become larger.     

Remarks on the Zeros of the Associated Legendre Functions with Integral Degree

We present some formulas for the computation of the zeros of the integral-degree associated Legendre functions with respect to the order. Work supported in part by the ‘Anillo Ecuaciones Asociadas a Reticulados’, financed by the World Bank through the ‘Programa Bicentenario de Ciencia y Tecnología’, and by the ‘Programa Reticulados y Ecuaciones’ of the Universidad de Talca.     

Impact on school assessment where use of graphics calculators is mandatory in a related public examination

This paper reports an inquiry into assessment items classed as 'extended pieces of work' in Applicable Mathematics, in Western Australia. The principal purpose was to identify opportunities for graphics calculator use in 'extended pieces' implemented in schools. Ownership of the technology is widespread because it is mandated for the Applicable Mathematics tertiary entrance examination, which students sit at the end of the Year 12 course. Twenty-one of the twenty-eight pieces that were collected allowed for calculator use and, frequently, choosing to use the technology would have advantaged students, for instance, in supporting conjecture. Practical applications that would not be feasible to solve without the technology were included. Regression analysis and the random number generator were utilized. Overall, availability of the technology has widened the scope of approaches in 'extended pieces of work' in potentially valuable ways. Issues are how conjectures were elicited and calls for 'black box' use of the calculator.     

Convergence analysis of a conforming adaptive finite element method for an obstacle problem

The adaptive algorithm for the obstacle problem presented in this paper relies on the jump residual contributions of a standard explicit residual-based a posteriori error estimator. Each cycle of the adaptive loop consists of the steps ‘SOLVE’, ‘ESTIMATE’, ‘MARK’, and ‘REFINE’. The techniques from the unrestricted variational problem are modified for the convergence analysis to overcome the lack of Galerkin orthogonality. We establish R-linear convergence of the part of the energy above its minimal value, if there is appropriate control of the data oscillations. Surprisingly, the adaptive mesh-refinement algorithm is the same as in the unconstrained case of a linear PDE—in fact, there is no modification near the discrete free boundary necessary for R-linear convergence. The arguments are presented for a model obstacle problem with an affine obstacle χ and homogeneous Dirichlet boundary conditions. The proof of the discrete local efficiency is more involved than in the unconstrained case. Numerical results are given to illustrate the performance of the error estimator.     

Complexity of Geometric Three-manifolds

We compute for all orientable irreducible geometric 3-manifolds certain complexity functions that approximate from above Matveev's natural complexity, known to be equal to the minimal number of tetrahedra in a triangulation. We can show that the upper bounds on Matveev's complexity implied by our computations are sharp for thousands of manifolds, and we conjecture they are for infinitely many, including all Seifert manifolds. Our computations and estimates apply to all the Dehn fillings of M 6 ₁ ³ (the complement of the three-component chain-link, conjectured to be the smallest triply cusped hyperbolic manifold), whence to infinitely many among the smallest closed hyperbolic manifolds. Our computations are based on the machinery of the decomposition into ‘bricks’ of irreducible manifolds, developed in a previous paper. As an application of our results we completely describe the geometry of all 3-manifolds of complexity up to 9.     

Calculator Use on NAEP: A Look at Fourth‐ and Eighth‐Grade Mathematics Achievement

This article summarizes research conducted on calculator block items from the 2007 fourth‐ and eighth‐grade National Assessment of Educational Progress Main Mathematics. Calculator items from the assessment were categorized into two categories: problem‐solving items and noncomputational mathematics concept items. A calculator has the potential to be used as a problem‐solving tool for items categorized in the first category. On the other hand, there are no practical uses for calculators for noncomputational mathematics concept items. Item‐level performance data were disaggregated by student‐reported calculator use to investigate the differences in achievement of those fourth‐ and eighth‐grade students who chose to use calculators versus those who did not, and whether or not the nation's fourth and eighth graders are able to identify items where calculator use serves as an aide for solving a given mathematical problem. Results from the analysis show that eighth graders, in particular, benefit most from the use of calculators on problem‐solving items. A small percentage of students at both grade levels attempted to use a calculator to solve problems in the noncomputational mathematics concept category (items in which the use of a calculator does not serve as a tool to solve the problem).     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.