TY - CHAP
TI - Factorization of polynomials given by straight-line programs
AU - Kaltofen, E.
T2 - Randomness and Computation, Advances in Computing Research
A2 - Micali, S.
PY - 1989///
VL - 5
SP - 375-412
PB - JAI Press Inc.
ER -
TY - CONF
TI - Parallel algebraic algorithm design
AU - Kaltofen, E.
T2 - 1989 International Symposium on Symbolic and Algebraic Computation
C2 - 1989/7//
CY - Portland, Oregon
DA - 1989/7//
PY - 1989/7//
PB - Rensselaer Polytechnic Institute, Department of Computer Science
ER -
TY - JOUR
TI - Learning to recognize students’ plan in geometry proof using intelligent CAI
AU - Okamoto, T.
AU - Matsuda, N.
T2 - Transactions of Information Processing Society of Japan
DA - 1989///
PY - 1989///
VL - 30
IS - 8
SP - 1046– 1057
ER -
TY - CHAP
TI - Improved sparse multivariate polynomial interpolation algorithms
AU - Kaltofen, Erich
AU - Yagati, Lakshman
T2 - Symbolic and Algebraic Computation
PY - 1989///
DO - 10.1007/3-540-51084-2_44
SP - 467–474
PB - Springer
SN - 9783540510840 9783540461531
UR - http://dx.doi.org/10.1007/3-540-51084-2_44
ER -
TY - BOOK
TI - Computers and Mathematics
A3 - Kaltofen, Erich
A3 - Watt, Stephen M.
DA - 1989///
PY - 1989///
DO - 10.1007/978-1-4613-9647-5
PB - Springer US
SN - 9780387970196 9781461396475
UR - http://dx.doi.org/10.1007/978-1-4613-9647-5
ER -
TY - CONF
TI - Computing the irreducible real factors and components of an algebraicf curve
AU - Kaltofen, E.
T2 - Fifth annual symposium on Computational geometry
A2 - Mehlhorn, K.
AB - We present algorithms that decompose an algebraic curve with rational coefficients in its defining bivariate equation into its irreducible real factors and its non-empty irreducible real components. We show that our algorithms are of polynomial bit complexity in the degree of the equation and the size of its coefficients. Our construction is based on computing the irreducible complex factors and then investigating high precision complex floating point coefficients of these factors and the complex norms.
C2 - 1989/6//
C3 - Proceedings of the fifth annual symposium on Computational geometry - SCG '89
DA - 1989/6//
PY - 1989///
DO - 10.1145/73833.73842
SP - 79-87
PB - ACM Press
SN - 0897913183 9780897913188
UR - http://dx.doi.org/10.1145/73833.73842
ER -
TY - CONF
TI - Solving systems of nonlinear polynomial equations faster
AU - Canny, J. F.
AU - Kaltofen, E.
AU - Yagati, L.
T2 - the ACM-SIGSAM 1989 international symposium
C2 - 1989///
C3 - Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89
DA - 1989///
DO - 10.1145/74540.74556
PB - ACM Press
SN - 0897913256
UR - http://dx.doi.org/10.1145/74540.74556
DB - Crossref
ER -
TY - CHAP
TI - Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal form of polynomial matrices
AU - Kaltofen, Erich
AU - Krishnamoorthy, M. S.
AU - Saunders, B. David
T2 - Lecture Notes in Computer Science
PY - 1989///
DO - 10.1007/3-540-51517-8_134
SP - 317-322
OP -
PB - Springer Berlin Heidelberg
SN - 9783540515173 9783540482079
UR - http://dx.doi.org/10.1007/3-540-51517-8_134
DB - Crossref
ER -
TY - JOUR
TI - Computing greatest common divisors and factorizations in quadratic number fields
AU - Kaltofen, Erich
AU - Rolletschek, Heinrich
T2 - Mathematics of Computation
AB - In a quadratic number field Q ( D ) {\mathbf {Q}}(\sqrt D ) , D a squarefree integer, with class number 1, any algebraic integer can be decomposed uniquely into primes, but for only 21 domains Euclidean algorithms are known. It was shown by Cohn [5] that for D ≤ − 19 D \leq - 19 even remainder sequences with possibly nondecreasing norms cannot determine the GCD of arbitrary inputs. We extend this result by showing that there does not even exist an input in these domains for which the GCD computation becomes possible by allowing nondecreasing norms or remainders whose norms are not as small as possible. We then provide two algorithms for computing the GCD of algebraic integers in quadratic number fields Q ( D ) {\mathbf {Q}}(\sqrt D ) . The first applies only to complex quadratic number fields with class number 1, and is based on a short vector construction in a lattice. Its complexity is O ( S 3 ) O({S^3}) , where S is the number of bits needed to encode the input. The second algorithm allows us to compute GCD’s of algebraic integers in arbitrary number fields (ideal GCD’s if the class number is > 1 > 1 ). It requires only O ( S 2 ) O({S^2}) binary steps for fixed D, but works poorly if D is large. Finally, we prove that in any domain, the computation of the prime factorization of an algebraic integer can be reduced in polynomial time to the problem of factoring its norm into rational primes. Our reduction is based on a constructive version of a theorem by A. Thue.
DA - 1989///
PY - 1989///
DO - 10.1090/s0025-5718-1989-0982367-2
VL - 53
IS - 188
SP - 697-697
J2 - Math. Comp.
LA - en
OP -
SN - 0025-5718
UR - http://dx.doi.org/10.1090/s0025-5718-1989-0982367-2
DB - Crossref
ER -
TY - CONF
TI - An improved Las Vegas primality test
AU - Kaltofen, E.
AU - Valente, T.
AU - Yui, N.
T2 - the ACM-SIGSAM 1989 international symposium
AB - We present a modification of the Goldwasser-Kilian-Atkin primality test, which, when given an input n, outputs either prime or composite, along with a certificate of correctness which may be verified in polynomial time. Atkin's method computes the order of an elliptic curve whose endomorphism ring is isomorphic to the ring of integers of a given imaginary quadratic field Q(√—D). Once an appropriate order is found, the parameters of the curve are computed as a function of a root modulo n of the Hilbert class equation for the Hilbert class field of Q(√—D). The modification we propose determines instead a root of the Watson class equation for Q(√—D) and applies a transformation to get a root of the corresponding Hilbert equation. This is a substantial improvement, in that the Watson equations have much smaller coefficients than do the Hilbert equations.
C2 - 1989///
C3 - Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89
DA - 1989///
DO - 10.1145/74540.74545
PB - ACM Press
SN - 0897913256
UR - http://dx.doi.org/10.1145/74540.74545
DB - Crossref
ER -
TY - JOUR
TI - Course Outline: Course Announcement (Spring 1989) CSE/OR 691 I: Surviving Intractability
AU - Stallmann, M.
T2 - SIGACT News
DA - 1989/11//
PY - 1989/11//
DO - 10.1145/74074.74086
VL - 20
IS - 4
SP - 74-77
UR - http://doi.acm.org/10.1145/74074.74086
ER -
TY - CONF
TI - Constrained planar embedding problems
AU - Stallmann, Matthias F.
C2 - 1989///
C3 - Proceedings 27th Annual Allerton Conference on Communication, Control, and Computing
DA - 1989///
SP - 58-67
ER -
TY - JOUR
TI - Constructive belief and rational representation
AU - Doyle, Jon
T2 - Computational Intell
AB - It is commonplace in artificial intelligence to divide an agent’s explicit beliefs into two parts: the beliefs explicitly represented or manifest in memory, and the implicitly represented or constructive beliefs that are repeatedly reconstructed when needed rather than memorized. Many theories of knowledge view the relation between manifest and constructive beliefs as a logical relation, with the manifest beliefs representing the constructive beliefs through a logic of belief. This view, however, limits the ability of a theory to treat incomplete or inconsistent sets of beliefs in useful ways. We argue that a more illuminating view is that belief is the result of rational representation. In this theory, the agent obtains its constructive beliefs by using its manifest beliefs and preferences to rationally (in the sense of decision theory) choose the most useful conclusions indicated by the manifest beliefs.
DA - 1989/1//
PY - 1989/1//
DO - 10.1111/j.1467-8640.1989.tb00311.x
VL - 5
IS - 1
SP - 1-11
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84990602501&partnerID=MN8TOARS
ER -
TY - CONF
TI - Adaptive routing and deadlock recovery: a simulation study
AU - Reeves, Douglas S.
AU - Gehringer, Edward F.
AU - Chandiramani, Anil
T2 - The Fourth Conference on Hypercube Concurrent Computers and their Applications
C2 - 1989///
C3 - Proceedings of the Fourth Conference on Hypercube Concurrent Computers and their Applications
CY - Monterey, CA
DA - 1989///
PY - 1989/3/6/
ER -
TY - JOUR
TI - Hypercube embedding heuristics: An evaluation
AU - Chen, Woei-Kae
AU - Stallmann, Matthias F. M.
AU - Gehringer, Edward F.
T2 - International Journal of Parallel Programming
AB - The hypercube embedding problem, a restricted version of the general mapping problem, is the problem of mapping a set of communicating processes to a hypercube multiprocessor. The goal is to find a mapping that minimizes the length of the paths between communicating processes. Unfortunately the hypercube embedding problem has been shown to be NP-hard. Thus many heuristics have been proposed for hypercube embedding. This paper evaluates several hypercube embedding heuristics, including simulated annealing, local search, greedy, and recursive mincut bipartitioning. In addition to known heuristics, we propose a new greedy heuristic, a new Kernighan-Lin style heuristic, and some new features to enhance local search. We then assess variations of these strategies (e.g., different neighborhood structures) and combinations of them (e.g., greedy as a front end of iterative improvement heuristics). The asymptotic running times of the heuristics are given, based on efficient implementations using a priority-queue data structure.
DA - 1989/12//
PY - 1989/12//
DO - 10.1007/bf01381720
VL - 18
IS - 6
SP - 505-549
J2 - Int J Parallel Prog
LA - en
OP -
SN - 0885-7458 1573-7640
UR - http://dx.doi.org/10.1007/bf01381720
DB - Crossref
ER -
TY - CONF
TI - Object-oriented design of finite element programs
AU - Baugh, John W.Jr
AU - Rehak, Daniel R.
C2 - 1989///
DA - 1989///
SP - 91-100
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0024863017&partnerID=MN8TOARS
ER -