TY - BOOK TI - Assessing the advantages of tagged architectures AU - Gehringer, Edward F. AU - Keedy, J.Leslie DA - 1985/// PY - 1985/// PB - Computer Studies Program, North Carolina State University ER - TY - RPRT TI - The integer manipulation techniques can compete with the linear algebra methods for solving sparse linear systems AU - Kaltofen, E. AU - Pan, V. A3 - State University of New York at Albany, Computer Science Department DA - 1985/// PY - 1985/// M1 - 85-6 M3 - Technical Report PB - State University of New York at Albany, Computer Science Department SN - 85-6 ER - TY - CONF TI - Granularity of parallel computation AU - Mohan, Joseph AU - Jones, Anita K. AU - Gehringer, Edward F. AU - Segall, Zary Z. T2 - The 18th Hawaii Conference on Systems Sciences A2 - Galizzi, Edmond L. C2 - 1985/1// C3 - Proceedings of the 18th Hawaii Conference on Systems Sciences DA - 1985/1// PY - 1985/1// VL - 1 SP - 249–256 ER - TY - CONF TI - Superlinear speedup through randomized algorithms AU - Mehrotra, Ravi AU - Gehringer, Edward F. T2 - The 14th International Conference on Parallel Processing C2 - 1985/// C3 - Proceedings of the 14th International Conference on Parallel Processing CY - St. Charles, IL DA - 1985/// PY - 1986/8/20/ SP - 291–300 ER - TY - JOUR TI - Factorization of multivariate polynomials over finite fields AU - von zur Gathen, J. AU - Kaltofen, E. T2 - Mathematics of Computation AB - We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field. DA - 1985/9/1/ PY - 1985/9/1/ DO - 10.1090/s0025-5718-1985-0790658-x VL - 45 IS - 171 SP - 251-251 J2 - Math. Comp. LA - en OP - SN - 0025-5718 UR - http://dx.doi.org/10.1090/s0025-5718-1985-0790658-x DB - Crossref ER - TY - JOUR TI - Effective Hilbert irreducibility AU - Kaltofen, Erich T2 - Information and Control AB - In this paper we prove by entirely elementary means a very effective version of the Hilbert irreducibility theorem. We then apply our theorem to construct a probabilistic irreducibility test for sparse multivariate polynomials over arbitrary perfect fields. For the usual coefficient fields the test runs in polynomial time in the input size. DA - 1985/9// PY - 1985/9// DO - 10.1016/s0019-9958(85)80056-5 VL - 66 IS - 3 SP - 123-137 J2 - Information and Control LA - en OP - SN - 0019-9958 UR - http://dx.doi.org/10.1016/s0019-9958(85)80056-5 DB - Crossref ER - TY - JOUR TI - Fast parallel absolute irreducibility testing AU - Kaltofen, Erich T2 - Journal of Symbolic Computation AB - We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coeffieients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial's irreducibility in the algebraic closure of the finite field of order p is not preserved. DA - 1985/3// PY - 1985/3// DO - 10.1016/s0747-7171(85)80029-8 VL - 1 IS - 1 SP - 57-67 J2 - Journal of Symbolic Computation LA - en OP - SN - 0747-7171 UR - http://dx.doi.org/10.1016/s0747-7171(85)80029-8 DB - Crossref ER - TY - CONF TI - Computing with polynomials given by straight-line programs II sparse factorization AU - Kaltofen, Erich T2 - 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) AB - We develop an algorithm for the factorization of a multivariate polynomial represented by a straight-line program into its irreducible factors represented as sparse polynomials. Our algorithm is in random polynomial-time for the usual coefficient fields and outputs with controllably high probability the correct factorization. It only requires an a priori bound for the total degree of the input and over rational numbers a bound on the size of the polynomial coefficients. C2 - 1985/// C3 - 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) DA - 1985/// DO - 10.1109/sfcs.1985.17 PB - IEEE SN - 0818606444 UR - http://dx.doi.org/10.1109/sfcs.1985.17 DB - Crossref ER - TY - CONF TI - Computing with polynomials given by straight-line programs I: greatest common divisors AU - Kaltofen, E T2 - the seventeenth annual ACM symposium AB - We develop algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation. Our algorithms are in random polynomial-time for the usual coefficient fields and output with controllably high probability the correct result which for the GCD problem is a straight-line program determining the GCD of the inputs and for the conversion algorithm is the sparse representation of the input. The algorithms only require an a priori bound for the total degrees of the inputs. Over rational numbers the conversion algorithm also needs a bound on the size of the polynomial coefficients. As specializations we get, e.g., random polynomial-time algorithms for computing the sparse GCD of polynomial determinants or for computing the sparse solution of a linear system whose coefficients are given by formulas. C2 - 1985/// C3 - Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 DA - 1985/// DO - 10.1145/22145.22160 PB - ACM Press SN - 0897911512 UR - http://dx.doi.org/10.1145/22145.22160 DB - Crossref ER - TY - JOUR TI - Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization AU - Kaltofen, Erich T2 - SIAM Journal on Computing AB - Consider a polynomial f with an arbitrary but fixed number of variables and with integral coefficients. We present an algorithm which reduces the problem of finding the irreducible factors of f in polynomial-time in the total degree of f and the coefficient lengths of f to factoring a univariate integral polynomial. Together with A. Lenstra’s,.H. Lenstra’s and L. Lovász’ polynomial-time factorization algorithm for univariate integral polynomials [Math. Ann., 261 (1982), pp. 515–534] this algorithm implies the following theorem. Factoring an integral polynomial with a fixed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree and the size of its coefficients. Our algorithm can be generalized to factoring multivariate polynomials with coefficients in algebraic number fields and finite fields in polynomial-time. We also present a different algorithm, based on an effective version of a Hilbert Irreducibility Theorem, which polynomial-time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polynomials for irreduciblity. DA - 1985/5// PY - 1985/5// DO - 10.1137/0214035 VL - 14 IS - 2 SP - 469-489 J2 - SIAM J. Comput. LA - en OP - SN - 0097-5397 1095-7111 UR - http://dx.doi.org/10.1137/0214035 DB - Crossref ER - TY - JOUR TI - Factoring sparse multivariate polynomials AU - von zur Gathen, Joachim AU - Kaltofen, Erich T2 - Journal of Computer and System Sciences AB - This paper presents a probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the size of sparse representations of input plus output, provided the number of irreducible factors is bounded. We thus obtain probabilistic polynomial-time factoring procedures over algebraic number fields and over finite fields. The reduction is based on an effective version of Hilbert's irreducibility theorem. DA - 1985/10// PY - 1985/10// DO - 10.1016/0022-0000(85)90044-3 VL - 31 IS - 2 SP - 265-287 J2 - Journal of Computer and System Sciences LA - en OP - SN - 0022-0000 UR - http://dx.doi.org/10.1016/0022-0000(85)90044-3 DB - Crossref ER - TY - CHAP TI - Sparse hensel lifting AU - Kaltofen, Erich T2 - EUROCAL '85 AB - A new algorithm is introduced which computes the multivariate leading coefficients of polynomial factors from their univariate images. This algorithm is incorporated into a sparse Hensel lifting scheme and only requires the factorization of a single univariate image. The algorithm also provides the content of the input polynomial in the main variable as a by-product. We show how we can take advantage of this property when computing the GCD of multivariate polynomials by sparse Hensel lifting. PY - 1985/// DO - 10.1007/3-540-15984-3_230 SP - 4-17 OP - PB - Springer Berlin Heidelberg SN - 9783540159841 9783540396857 UR - http://dx.doi.org/10.1007/3-540-15984-3_230 DB - Crossref ER - TY - JOUR TI - Expert Systems and the “Myth” of Symbolic Reasoning AU - Doyle, J. T2 - IEEE Transactions on Software Engineering AB - Elements of the artificial intelligence approach to expert systems offer great productivity advantages over traditional approaches to application systems development, even though the end result may be a program employing no AI techniques. These productivity advantages are the hidden truths behind the "myth" that symbolic reasoning programs are better than ordinary ones. DA - 1985/// PY - 1985/// DO - 10.1109/TSE.1985.231886 VL - SE-11 IS - 11 SP - 1386-1390 UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0022132767&partnerID=MN8TOARS ER - TY - RPRT TI - Using PQ-trees for planar embedding problems AU - Stallmann, Matthias A3 - North Carolina State University. Dept. of Computer Science DA - 1985/// PY - 1985/// PB - North Carolina State University. Dept. of Computer Science ER - TY - CONF TI - Efficient algorithms for graphic matroid intersection and parity AU - Gabow, Harold N AU - Stallmann, Matthias T2 - Springer, Berlin, Heidelberg C2 - 1985/// C3 - International Colloquium on Automata, Languages, and Programming DA - 1985/// SP - 210-220 ER - TY - JOUR TI - Circumscription and implicit definability AU - Doyle, Jon T2 - J Autom Reasoning AB - We explore some connections between the technique of circumscription in artificial intelligence and the notion of implicit definition in mathematical logic. Implicit definition can be taken as the informal intent, but not necessarily the formal result, of circumscription. This raises some questions for logical theory and suggests some implications for artificial intelligence practice. The principal implication is that when circumscription ‘works’ its conclusions can be explicitly described. DA - 1985/// PY - 1985/// DO - 10.1007/bf00244277 VL - 1 IS - 4 SP - 391-405 UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0022279687&partnerID=MN8TOARS ER - TY - RPRT TI - Assessing the advantages of tagged architectures AU - Gehringer, Edward F. AU - Keedy, J.Leslie A3 - Computer Studies Program, North Carolina State University DA - 1985/5// PY - 1985/5// M1 - TR-85-08 M3 - Technical report PB - Computer Studies Program, North Carolina State University SN - TR-85-08 ER - TY - JOUR TI - The influence of parallel decomposition strategies on the performance of multiprocessor systems AU - Vrsalovic, Dalibor AU - Gehringer, Edward F. AU - Segall, Zary Z. AU - Siewiorek, Daniel P. T2 - ACM SIGARCH Computer Architecture News AB - article The influence of parallel decomposition strategies on the performance of multiprocessor systems Share on Authors: Dalibor Vrsalovic Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Edward F. Gehringer Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Zary Z. Segall Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Daniel P. Siewiorek Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 396–405https://doi.org/10.1145/327070.327372Online:01 June 1985Publication History 26citation241DownloadsMetricsTotal Citations26Total Downloads241Last 12 Months1Last 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 DA - 1985/6/1/ PY - 1985/6/1/ DO - 10.1145/327070.327372 VL - 13 IS - 3 SP - 396-405 J2 - SIGARCH Comput. Archit. News LA - en OP - SN - 0163-5964 UR - http://dx.doi.org/10.1145/327070.327372 DB - Crossref ER - TY - JOUR TI - Tagged architecture AU - Gehringer, Edward F. AU - Keedy, J. Leslie T2 - ACM SIGARCH Computer Architecture News AB - article Free Access Share on Tagged architecture: how compelling are its advantages? Authors: Edward F. Gehringer Department of Electrical and Computer Engineering, North Carolina State University Department of Electrical and Computer Engineering, North Carolina State UniversityView Profile , J. Leslie Keedy Department of Mathematics and Computer Science, University of Newcastle Department of Mathematics and Computer Science, University of NewcastleView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 162–170https://doi.org/10.1145/327070.327153Online:01 June 1985Publication History 12citation871DownloadsMetricsTotal Citations12Total Downloads871Last 12 Months98Last 6 weeks20 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 DA - 1985/6/1/ PY - 1985/6/1/ DO - 10.1145/327070.327153 VL - 13 IS - 3 SP - 162-170 J2 - SIGARCH Comput. Archit. News LA - en OP - SN - 0163-5964 UR - http://dx.doi.org/10.1145/327070.327153 DB - Crossref ER - TY - CONF TI - Food Animal Residue Avoidance Databank AU - Riviere, J. E. AU - Craigmill, A. L. AU - Sundlof, S. F. C2 - 1985/// C3 - Proceedings of the Food Science Symposium VI: Assuring Meat Wholesomeness, The Residue Avoidance Issue DA - 1985/// SP - G1-5 ER -