LogicWriter Actual (https://tinyurl.com/logicwriteractual) is a web app that helps early undergraduate CS students write with symbolic logic notation (↔, ∃, ∧, Greek letters, etc.). It designed with a quick start easy-to-use interface and is compatible with most writing programs. LogicWriter Actual is designed to minimize cognitive demands on software operation so that students can focus on mathematical writing.

"Proof Buddy" is an online browser based tool designed to teach proof writing to beginning computer science students. It has been designed from the ground up with educational purposes in mind and has been used successfully with hundreds of students since January 2022 at Drexel University. The tool helps students build and check proofs in a variety of systems. It is capable of doing Natural Deduction, both Boolean logic and first order logic, and is being extended to Equational Reasoning. Important instructor-centered features include that the teacher can create assignments of proof problems, which the software can auto score and have results uploaded into their school's LMS. Additionally, the tool allows proofs to be saved and exported and used as new rules. When this feature is used by the instructor, it permits a customization of the allowable rules. When this feature is used by the students, it allows them to create their own lemmas which reduces the cognitive load of a more intricate proof.

The exact probability, dependent on the matrix structure, is given that the block Wiedemann algorithm correctly computes the leading invariant factors of a matrix. A tight lower bound, structure independent, is derived.

We investigated the impact of assigning specific roles in Process Oriented Guided Inquiry Learning (POGIL) activities versus giving the same group activities without pre-assigned roles. We hoped to show that the group with additional structure would receive tangible benefits: more engagement with partners, greater comprehension of material, heightened content interest, and increased retention. Preliminary results suggest that the proportion of minimally participating students was not statistically significantly different, and neither were the individual assessments. The roled section did have higher scores overall in the course, both in the group activities and also in the final exam; however, the difference was small and not clearly statistically significant. Unexpectedly, disciplinary actions and post course surveys indicate a greater rate of plagiarism on both shared lab reports and individual homework assignments in the free-form group and this may be a factor for instructors to bear in mind when utilizing group activities.

In this paper, we address the question of how to automatically map computational kernels to highly efficient code for a wide range of computing platforms and establish the correctness of the synthesized code. More specifically, we focus on two fundamental problems that software developers are faced with: performance portability across the ever-changing landscape of parallel platforms and correctness guarantees for sophisticated floating-point code. The problem is approached as follows: We develop a formal framework to capture computational algorithms, computing platforms, and program transformations of interest, using a unifying mathematical formalism we call operator language (OL). Then we cast the problem of synthesizing highly optimized computational kernels for a given machine as a strongly constrained optimization problem that is solved by search and a multistage rewriting system. Since all rewrite steps are semantics preserving, our approach establishes equivalence between the kernel specification and the synthesized program. This approach is implemented in the SPIRAL system, and we demonstrate it with a selection of computational kernels from the signal and image processing domain, software-defined radio, and robotic vehicle control. Our target platforms range from mobile devices, desktops, and server multicore processors to large-scale high-performance and supercomputing systems, and we demonstrate performance comparable to expertly hand-tuned code across kernels and platforms.

Building a reusable, auto-tuning code generator from scratch is a challenging problem, requiring many careful design choices. We describe HSpiral, a Haskell compiler for signal transforms that builds on the foundational work of Spiral. Our design leverages many Haskell language features to ensure that our framework is reusable, flexible, and efficient. As well as describing the design of our system, we show how to extend it to support new classes of transforms, including the number-theoretic transform and a variant of the split-radix algorithm that results in reduced operation counts. We also show how to incorporate rewrite rules into our system to reproduce results from previous literature on code generation for the fast Fourier transform.

This session invites educators interested in sharing and/or learning about experiences with tools for automatic feedback on technical work: the "if", "why" and "how". This includes experiences with program testing, problem-solving exercises, or quizzes, generated or checked with engines with expert-level technical capabilities, to scale up feedback to cope with burgeoning enrollment in CS courses while maintaining or improving student learning outcomes. Commercial, free and open-source tools now exist to assist in this endeavor.

This paper reports on a high-performance implementation of the truncated Fourier transform (TFT). A general Cooley-Tukey like algorithm for the TFT is developed that allows the implementation to automatically adapt to the memory hierarchy. Then the algorithm introduces a small relaxation for larger transform sizes which trades off slightly higher arithmetic cost for improved data flow which allows full vectorization and parallelization. The implementation is automatically derived and tuned using the SPIRAL system for code generation and adaptation. The resulting arbitrary-size TFT library smooths out the staircase performance associated with power-of-two modular FFT implementations while retaining the performance associated with state-of-the-art FFT libraries. This provides significant performance improvement over approaches that pad to the next power of two even when using high-performance FFT libraries.

The calculus of moving surfaces (CMS) is an analytic framework that extends the tensor calculus to deforming manifolds. We have applied the CMS to a number of boundary variation problems using a Term Rewrite System (TRS). The TRS is used to convert the initial CMS expression into a form that can be evaluated. The CMS produces expressions that are true for all coordinate spaces. This makes it very powerful but applications remain limited by a rapid growth in the size of expressions. We have extended results on existing problems to orders that had been previously intractable. In this paper, we describe our TRS and our method for evaluating CMS expressions on a specific coordinate system. Our work has already provided new insight into problems of current interest to researchers in the CMS.

We present a domain-specific approach to generate high-performance hardware-software partitioned implementations of the discrete Fourier transform (DFT) in fixed point precision. The partitioning strategy is a heuristic based on the DFT's divide-and-conquer algorithmic structure and fine tuned by the feedback-driven exploration of candidate designs. We have integrated this approach in the Spiral linear-transform code-generation framework to support push-button automatic implementation. We present evaluations of hardware-software DFT implementations running on the embedded PowerPC processor and the reconfigurable fabric of the Xilinx Virtex-II Pro FPGA. In our experiments, the 1D and 2D DFT's FPGA-accelerated libraries exhibit between 2 and 7.5 times higher performance (operations per second) and up to 2.5 times better energy efficiency (operations per Joule) than the software-only version.

This paper presents a code generator which produces efficient implementations of multi-dimensional fast Fourier transform (FFT) algorithms which utilize symmetries in the input data to reduce memory usage and the number of arithmetic operations. The FFT algorithms are constructed using a group theoretic version of the divide and conquer step in the FFT that is compatible with the group of symmetries. The GAP compute algebra system is used to perform the necessary group computations and the generated algorithm is represented as a symbolic matrix factorization, which is translated into efficient code using the SPIRAL system. Performance data is given that shows that the resulting code is significantly faster than state-of-the-art FFT implementations that do not utilize the symmetries.

The Descartes method for polynomial real root isolation can be performed with respect to monomial bases and with respect to Bernstein bases. The first variant uses Taylor shift by 1 as its main subalgorithm, the second uses de Casteljau's algorithm. When applied to integer polynomials, the two variants have co-dominant, almost tight computing time bounds. Implementations of either variant can obtain speed-ups over previous state-of-the-art implementations by more than an order of magnitude if they use features of the processor architecture. We present an implementation of the Bernstein-bases variant of the Descartes method that automatically generates architecture-aware high-level code and leaves further optimizations to the compiler. We compare the performance of our implementation, algorithmically tuned implementations of the monomial and Bernstein variants, and architecture-unaware implementations of both variants on four different processor architectures and for three classes of input polynomials.

We present algorithms that outperform straightforward implementations of classical Taylor shift by 1. For input poly-nomials of low degrees a method of the SACLIB library is faster than straightforward implementations by a factor of at least 2; for higher degrees we develop a method that is faster than straightforward implementations by a factor of up to 7. Our Taylor shift algorithm requires more word additions than straightforward methods but it reduces the number of cycles per word addition by reducing memory traffic and the number of carry computations. The introduction of signed digits, suspended normalization, radix reduction, and delayed carry propagation enables our algorithm to take advantage of the technique of register tiling which is commonly used by optimizing compilers. While our algorithm is written in a high-level language, it depends on several parameters that can be tuned to the underlying architecture.

Fast changing, increasingly complex, and diverse computing platforms pose central problems in scientific computing: How to achieve, with reasonable effort, portable optimal performance? We present SPIRAL, which considers this problem for the performance-critical domain of linear digital signal processing (DSP) transforms. For a specified transform, SPIRAL automatically generates high-performance code that is tuned to the given platform. SPIRAL formulates the tuning as an optimization problem and exploits the domain-specific mathematical structure of transform algorithms to implement a feedback-driven optimizer. Similar to a human expert, for a specified transform, SPIRAL "intelligently" generates and explores algorithmic and implementation choices to find the best match to the computer's microarchitecture. The "intelligence" is provided by search and learning techniques that exploit the structure of the algorithm and implementation space to guide the exploration and optimization. SPIRAL generates high-performance code for a broad set of DSP transforms, including the discrete Fourier transform, other trigonometric transforms, filter transforms, and discrete wavelet transforms. Experimental results show that the code generated by SPIRAL competes with, and sometimes outperforms, the best available human tuned transform library code.

This work discusses an FPGA implementation study of the Bene Permutation Network (BPN). The BPN, originally developed for connecting devices in telephone switching, is a circuit of size O(n log n) and O(log n) depth, built from 2 x 2 switches, which is capable of performing an arbitrary permutation. The BPN provides an asymptotic improvement in area over the straightforward network built with multiplexers, and the work presented here shows that an FPGA implementation uses less area for networks as small as size 4. The implementation presented in this paper uses a special-purpose tool to synthesize and place and route the circuit. The place and route tool can be used to systematically explore alternative place and route strategies and was used to obtain significantly better area utilization and timing performance compared to general-purpose tools. In addition, several general improvements and extensions were discovered that further improve performance and reduce area.

Summary form only given. We present a self-adapting distributed memory package for computing the Walsh-Hadamard transform (WHT), a prototypical fast signal transform, similar to the fast Fourier transform. A family of distributed memory algorithms are derived from different factorizations of the WHT matrix. Different factorizations correspond to different data distributions and communication patterns. Thus, searching over the space of factorizations leads to the best data distribution and communication pattern for a given platform. The distributed memory WHT package provides a framework for converting factorizations of the WHT matrix into MPl programs and exploring their performance by searching the space of factorizations.

We discuss the design and implementation of a compiler that translates formulas representing signal processing transforms into efficient C or Fortran programs. The formulas are represented in a language that we call SPL, an acronym from Signal Processing Language. The compiler is a component of the SPIRAL system which makes use of formula transformations and intelligent search strategies to automatically generate optimized digital signal processing (DSP) libraries. After a discussion of the translation and optimization techniques implemented in the compiler, we use SPL formulations of the fast Fourier transform (FFT) to evaluate the compiler. Our results show that SPIRAL, which can be used to implement many classes of algorithms, produces programs that perform as well as “hard-wired” systems like FFTW.

This paper describes an approach to implementing and optimizing fast signal transforms. Algorithms for computing signal transforms are expressed by symbolic expressions, which can be automatically generated and translated into programs. Optimizing an implementation involves searching for the fastest program obtained from one of the possible expressions. We apply this methodology to the implementation of the Walsh-Hadamard transform. An environment, accessible from MATLAB, is provided for generating and timing WHT algorithms. These tools are used to search for the fastest WHT algorithm. The fastest algorithm found is substantially faster than standard approaches to implementing the WHT. The work reported in this paper is part of the SPIRAL project. An ongoing project whose goal is to automate the implementation and optimization of signal processing algorithms.

Article Software components using symbolic computation for problem solving environments Share on Authors: Y. N. Lakshman Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA Department of Mathematics and Computer Science, Drexel University, Philadelphia, PAView Profile , Bruce Char Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA Department of Mathematics and Computer Science, Drexel University, Philadelphia, PAView Profile , Jeremy Johnson Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA Department of Mathematics and Computer Science, Drexel University, Philadelphia, PAView Profile Authors Info & Claims ISSAC '98: Proceedings of the 1998 international symposium on Symbolic and algebraic computationAugust 1998 Pages 46–53https://doi.org/10.1145/281508.281542Online:01 August 1998Publication History 9citation341DownloadsMetricsTotal Citations9Total Downloads341Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper reports on the use of TechTalk, a web based chat environment designed for scientific and mathematical collaboration, in mathematics instruction. Techtalk provides internet access to shared Maple and MATLAB sessions and the ability to conduct a multiway conversation. Using this feature an instructor is able to answer questions on Maple/MATLAB outside of the classroom and outside of conventional, face-to-face office hours.

A method is presented for isolating and refining the real roots of polynomials with either integer or real algebraic number coefficients. For root isolation the method uses a well-known algorithm that is based on Descartes' rule of signs. However, exact arithmetic is replaced as far as possible by validated double precision floating point arithmetic. The resulting method is powerful and very fast.

An algorithm is described for multiplying multiprecision floating-point numbers. The algorithm can produce either the smallest floating-point number greater than or equal to the true product, or the greatest floating-point number smaller than or equal to the true product. Software implementations of multiprecision floating-point multiplication can reduce the computation time by a factor of two if they do not compute the low-order digits of the product of the two mantissas. However, these algorithms do not necessarily provide optimally rounded results. The algorithms described here is guaranteed to produce optimally rounded results and typically obtains the same savings.>

Article Free Access Share on Real algebraic number computation using interval arithmetic Author: J. R. Johnson View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 195–205https://doi.org/10.1145/143242.143311Online:01 August 1992Publication History 6citation426DownloadsMetricsTotal Citations6Total Downloads426Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors present an algebraic theory based on tensor products for modeling direct interconnection networks. This theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. This theory can be used for mapping algorithms expressed in tensor product form onto distributed-memory architectures. The authors focus on the modeling of direct interconnection networks. Rings, n-dimensional meshes, and hypercubes are represented in tensor product form. Algorithm mapping using tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks.>

Article Free Access Share on Quantifier elimination and the sign variation method for real root isolation Authors: G. E. Collins Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile , J. R. Johnson Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computationJuly 1989 Pages 264–271https://doi.org/10.1145/74540.74574Online:17 July 1989Publication History 9citation342DownloadsMetricsTotal Citations9Total Downloads342Last 12 Months7Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF