Archive for the ‘US PATENT APPLICATION RESEARCH’ Category

Metablogging. ¡¡ Estoy hasta los h…!!

febrero 26, 2017

(more…)

IP. Solicitar hoy una patente en EEUU: la visión de los inventores.

enero 29, 2017

Varios artículos sobre la travesía del desierto en que se ha convertido el solicitar una patente hoy en EEUU. Posiblemente sean artículos algo sesgados (hacia una visión demasiado crítica) y que intentan aprovechar la coyuntura (nueva presidencia en EEUU con una política de patentes al parecer bastante indefinida de momento) para presionar y que haya un cambio de rumbo. Realmente me gustaría ver algunas estadísticas para emitir un juicio.

El problema ya no es sólo conseguir la concesión de la patente (cosa que en determinados campos como en las patentes de software, se ha convertido en misión imposible; doy fe, pero sin que sirva de precedente no vamos a entrar en detalles sobre mi caso en esta entrada).

Los problemas sobre los que hablan son todos post-conceisón o post-grant.  Es decir, cuando te la han concedido te esperan, según nos informan en los artículos a los que enlazamos, múltiples nuevas dificultades que yo desconocía (no hablo de dificultades en la comercialización / rentabilización, que ya conocía, sino de litigaciones post-concesión por parte de terceras partes; me voy a empezar a informar; de momento, dados los plazos de la tramitación, yo ya llevo más de 8 años, he aplicado la regla según va viniendo vamos viendo) pero que de realizarse pueden dejar completamente fuera de juego a cualquier inventor con unas posibilidades financieras limitadas.

Según nos comentan en los artículos, lo cierto es que el sistema se ha desequilibrado (de manera claramente consciente por parte de los tres poderes de EEUU: ejecutivo, legislativo y judicial) hacía los grandes jugadores, es decir la multinacionales americanas que campan a  sus anchas (y no sólo en este aspecto). Seguramente los tres poderes han tratado de proteger a la gallina de los huevos de oro. Al parecer todo empezó en 2006 y se ha ido intensificando desde entonces tras múltiples y activas campañas de lobbying por parte de estas multinacionales. Ahora, además de atropellar, también les sale prácticamente gratis robar.

¿ Puede haber cambios al respecto con la nueva presidencia a favor de los pequeños inventores ? Esperemos acontecimientos. Hasta que se despejen las incógnitas, para los pequeños inventores domiciliados en EEUU hay esperanzas. Creo recordar que hubo alguna presidencia (ahora no recuerdo cual) que le plantó cara a la gran empresa. Pero este no es mi caso, yo no tengo domicilio en EEUU. Teniendo en cuenta la deriva nacionalista que está tomando la nueva presidencia (es muy pronto para llegar a conclusiones, pero ya se ven señales claras), no espero nada. Por supuesto no pienso que pueda haber una instrucción genérica para mi caso, pero sí podría haber (aunque lo dudo) una instrucción genérica para patentes solicitadas por extranjeros.

En fin sin más preliminares los enlaces indicados:

Una  entrada de un inventor en serie (que ha comercializado varias de sus patentadas invenciones) y que ha decidido abandonar su última solicitud ya que los costes y riesgos son mucho mayores que los posibles beneficios.

Nota.

Yo no voy a abandonar mi segunda solicitud. Pero en mi vida me meteré en otra patente, aunque acabe rentabilizando estas dos primeras, cosa que dudo por lo ya indicado (según voy leyendo, estoy más pesimista que nunca). Y recomiendo activa y encarecidamente a cualquiera que lea estas líneas que dedique su tiempo a cualquier otra actividad que no sea inventar. Dadas las circunstancias, será una pérdida de tiempo sí o sí: la vía de la patente es una vía muerta y las otras (el secreto comercial) en mi opinión también, pues te dejan muy poco margen.

Fin de nota.

–Y dos entradas de otro inventor en serie que también ha rentabilizado anteriores patentadas invenciones. También con un mensaje todo menos incentivador. La primera y la segunda.  Las dos bastante técnicas.

Algorítmica y complejidad computacional. Un nuevo estilo / problema en matemáticas.

enero 26, 2017

Lo hemos comentado muy recientemente en una entrada anterior (perdón por la autocita).

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Se ha publicado una interesante entrada en el blog GLL en la que hablan sobre este  mismo tema

The issue is simple:

Someone writes up a paper that “proves” that X is true, where X is some hard open problem. How do we check that X is proved?

The proof in question is almost always long and complex. So the checking is not a simple matter. In some cases the proof might even use nonstandard methods and make it even harder to understand.

y comentan sobre las posibles reacciones a este nuevo estilo de matemáticas.  Recomendamos su lectura.

(more…)

Algorítmica y complejidad computacional. Otra conjetura (dicotomia Feder-Vardi en CSPs) posiblemente resuelta.

enero 12, 2017

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Me interesé en las dicotomías relacionadas con CSP en su momento, cuando estudiaba sobre temas de complejidad computacional. Esta dicotomía además tiene que ver con digrafos, en los que tenemos interés en general. Y para más inri tiene que ver con homomorfismos entre digrafos y uno de los pasos de nuestro método es precisamente un homomorfismo entre digrafos. Por lo tanto vamos a hacer seguimiento. Pero ojo, no estamos afirmando que este resultado tenga nada que ver con el nuestro.

El artículo:  Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity polymorphism ϕ then deciding whether G admits a homomorphism to H (HOM(H)) is polynomial time solvable. This confirms the conjecture of Bulatov, Jeavons, and Krokhin, in the form postulated by Maroti and McKenzie, and consequently implies the validity of the celebrated dichotomy conjecture due to Feder and Vardi. We transform the problem into an instance of the list homomorphism problem where initially all the lists are full (contain all the vertices of H). Then we use the polymorphism ϕ as a guide to reduce the lists to singleton lists, which yields a homomorphism if one exists.

el blog dónde he visto la noticia.

Algorítmica y complejidad computacional. El problema P vs. NP, un survey.

enero 8, 2017

El autor del survey es el merecidamente popular bloguero (y por supuesto académico experto en computación cuántica) Aaronson.

Lo he leído muy muy en diagonal este finde aprovechando que tenía un potente resfriado, lo cual en general y paradójicamente me inspira. Me ha gustado sobre todo (y mucho) el punto 6, en el que he concentrado mi tiempo. Los otros puntos, que finalmente me he saltado, diría que no aportan demasiado a cualquiera que ya conozca el tema (aunque yo lo tengo completamente oxidado y me vendría bien un recordatorio, así que lo leeremos más detalladamente en otra ocasión).

El punto 6 repasa las barreras o limitaciones teóricas que se han encontrado (y se pueden encontrar) en los intentos de demostraciones de esta conjetura (tema muy bien explicado que finalmente creo que he comprendido, pero que nadie me pida que se lo explique ahora :-); nos demuestran que hay niveles de abstracción inadecuados o más bien insuficientes para atacar este problema, sea por exceso o sea por defecto, lo cual da que pensar; realmente los nombres elegidos para las denominarlas no dicen mucho de lo que luego son) así como algunos enfoques prometedores, que permiten saltarse estas barreras (aunque a lo mejor se encontrarán con otras) como el utilizar cotas superiores algorítmicas para demostrar cotas  inferiores teóricas y así separar clases de complejidad (método que ya ha dado sus frutos hace unos años, separando dos clases de complejidad, eso sí muy extremas; también tiene un nombre raro) o el enfoque llamado Geometric Complexity Theory que aplica técnicas de geometría algebraica (el estudio de los conjuntos de soluciones de los sistemas de ecuaciones algebraicases decir a ecuaciones polinómicas multivariables, cuando las variables recorren determinados tipos de estructuras algebraicas) a estos temas. Gracias a este survey también he comprendido este último enfoque, obviamente en líneas muy muy generales (idem, que  nadie me pida que se lo explique…).  El autor no entra en demasiados detalles técnicos al respecto, lo cual algunos agradecerán, pero nos da una visión de (un) pájaro con muy buena vista. Por lo visto a algunos expertos este enfoque les parece una complicación innecesaria; a otros un camino viable.

Espero lector, que disfrutes del  survey.

Por cierto, al leerlo me he acordado de un tema que tenemos pendiente de comprobar con respecto a nuestro método de demostración de no hamiltonicidad en casos, que bien por ser entangled o twisted, no tienen recorridos hamiltonianos, método que hemos detallado largamente en varias entradas el pasado verano: ¿ como escala este método con el tamaño del input ?.

Ya en el peor caso, sólo determinar o decidir si un caso es entangled puede ser subexponencial (cota de Landau). Si es entangled el caso es potencialmente complicado y ya podemos decidir abandonarlo sin más e identificar otro que sea potencialmente sencillo.

Pero si por los motivos que sean nos gustan sus propiedades conocidas y además queremos que tenga recorridos hamiltonianos luego hay una serie de pasos más que nos permiten demostrar que no los tiene y aplicar el  razonamiento contrapositivo, según hemos detallado en las entradas del año pasado. Así de memoria pensamos no incrementarán la cota teórica señalada en el peor caso (según pienso hablaríamos de una suma de operaciones de complejidad subexponencial, lo cual sólo añadiría constantes). Pero queremos comprobarlo.

De  cualquier manera ya la cota subexponencial peor caso sólo para decidir si el caso es entangled nos deja completamente insatisfechos…Por otra parte también hemos comentado en varias entradas anteriores que hay buenos argumentos para pensar que el caso medio no será subexponencial, sino más bien cuasipolinómico (ver también aquí), lo cual nos consuela. Por otra parte de momento no hemos investigado si hay un test más eficiente para identificar si un caso tiene las propiedades de entrelazado (entanglement) o de retorcimiento (twistedness). No me parece fácil mejorar el  estado del arte en esto, pero tampoco imposible.

Algunos extractos (barriendo para casa :-)):

 –2.2.1 Search, Decision, and Optimization . . . . . . . . . . . . . . . . . . . . . . . . 16

Es un extracto del índice. En el punto indicado nos explica la diferencia entre estos problemas (también la no diferencia desde el punto de vista de complejidad computacional). ¿ Por qué es tan complicado entender esta diferencia ?

–Just as Hilbert’s question turned out to have a negative answer, so too in this case, most computer scientists conjecture that P!= NP: that there exist rapidly checkable problems that aren’t rapidly solvable, and for which brute-force search is close to the best we can do. This is not a unanimous opinion. At least one famous computer scientist, Donald Knuth [151], has professed a belief that P = NP, while another, Richard Lipton [171], professes agnosticism.   

Desconocía esta posición de Knuth tan extrema (bastante reciente; la referencia es: D. E. Knuth and E. G. Daylight. Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014; se trata de una entrevista). Si conocía la del otro investigador pues leemos su blog. Son, dicho sea con todos los respetos, dos veteranos que ya no tienen nada que demostrar a nadie ni nada que temer y, a calzón quitao, muestran un escepticismo a contracorriente muy sano y recomendable, que equilibra la balanza. Hace poco hicimos una entrada sobre otro investigador, más joven, que también expresaba sus dudas abiertamente.

–More broadly, there are many cases in mathematics where we can prove that some object O of interest to us has a property P, even though we have no hope of finding a general polynomial time algorithm to decide whether any given object has property P, or even to certify a large fraction of objects as having property P. In such cases, often we prove that O has property P by exploiting special symmetries in O—symmetries that have little to do with why O has property P, but everything to do with why we can prove it has the property. As an example, a random graph is an expander graph (that is, a graph on which a random walk mixes rapidly) with overwhelming probability. But since the general problem of deciding whether a graph is an expander is NP-hard, if we want a specific graph G that’s provably an expander, typically we need to construct G with a large amount of symmetry: for example, by taking it to be the Cayley graph of a finite group. Similarly, even though we expect that there’s no general efficient algorithm to decide if a Boolean function f is hard,51 given as input f’s truth table, we might be able to prove that certain specific f’s (for example, NP- or #P-complete ones) are hard by exploiting their symmetries. Geometric Complexity Theory (see Section 6.6) is the best-known development of that particular hope for escaping the natural proofs barrier.

Esta es la única mención honorífica a los Grafos de Cayley en todo el survey, en un contexto perfectamente conocido desde hace años. Pero lo hemos extractado sobre todo porque es una prueba más del hecho de que demostrar que un grafo tiene determinadas propiedades, y sólo esto, añade valor. Cosa que de nuevo parece que a algunos les cuesta comprender.

–ETH is an ambitious strengthening of P!= NP. Even assuming P!= NP, there’s by no means a consensus in the field that ETH is true—let alone still further strengthenings, like the Strong Exponential Time Hypothesis or SETH, which asserts that any algorithm for kSat requires Ω ((2 − ε) n ) time, for some ε that goes to zero as k → ∞. SETH, of course, goes even further out on a limb than ETH does, and some algorithms researchers have been actively working to disprove SETH (see [275] for example).

En el blog nos hemos interesado bastante por la conjetura ETH hace años.

–But now we come to the main insight of GCT, which is that the permanent and determinant are both special, highly symmetric functions, and it’s plausible that we can leverage that fact to learn more about their orbit closures than we could if they were arbitrary functions. For starters, Per (X) is symmetric under permuting X’s rows or columns, transposing X, and multiplying the rows or columns by scalars that multiply to 1. That is, we have

Per (X) = Per ( XT ) = Per (P XQ) = Per (AXB) (2)

for all permutation matrices P and Q, and all diagonal matrices A and B such that Per (A) Per (B) = 1.

The determinant has an even larger symmetry group: we have

Det (X) = Det ( XT ) = Det (AXB) 

Nos gusta la simetría. Muy interesante. En esto se basa todo el enfoque GCT, al parecer.

Algorítmica y Complejidad Computacional. Recopilación de enlaces, noviembre 2016: Redes de Interconexión, Grafos de Cayley, Recorridos Hamiltonianos, Permutaciones y otros. 

noviembre 30, 2016

Una recopilación de artículos sobre los temas que aparecen en el título, realizada en fechas varias, la última esta misma mañana (por el lunes), en la cual he encontrado cosas muy interesantes con respecto a potenciales aplicaciones. Aunque ya se sabe que entre la ingeniería apegada a la tierra y las elevadas matemáticas se encuentra el limbo de potenciales aplicaciones que nunca terminarán de concretarse en sistemas reales.

Antes de empezar con los enlaces un extracto de una muy reciente entrada en un blog de un experto en complejidad computacional. Creo que es reseñable ya que la declaración es sorprendente, contundente y va contracorriente:

The bottom line of this post is that we can’t prove lower bounds because they are false, and it is a puzzle to me why some people appear confident that P is different from NP.

Añadido a última hora.

On the Complexity of the Word Problem of Automaton Semigroups and Automaton Groups

I. Enfoque de ingeniería de redes: redes de interconexión (supercomputadores, NoC´s, Data Center Networks).

Data center interconnection networks are not hyperbolic

David Coudert1,2 and Guillaume Ducoffe2,1 1 Inria, France 2Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, 06900 Sophia Antipolis, France

Abstract Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

–Muy interesante. Y muy reciente, de 2016.

The Influence of Datacenter Usage on Symmetry in Datacenter Network Design

Alejandro Ericksona , Iain A. Stewarta,∗ aSchool of Engineering and Computing Sciences, Durham University, South Road, Durham DH1 3LE, U.K.

Abstract We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multi-tenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning-trees, pancyclicity, and variations of Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graphtheoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.

Extractos.

Whilst the design of DCNs is more recent, it has much in common with general interconnection network design yet there are profound differences too, prompted by, for example, usage, scale, and packaging. Hitherto, the most common metrics used for DCN evaluation are the availability of routing algorithms, hardware cost (e.g., number of servers and switches), hardware complexity (e.g., number of server-ports), diameter, bisection width, connectivity, and shortest-path lengths. It is probably fair to say that the development of appropriate topological metrics for DCNs is not as advanced as it is for distributed-memory multiprocessors and networks-onchips, and that the validity of these topological metrics within a datacenter environment is not as well established. Our paper seeks to strengthen the role of topological metrics in DCN design.

Our work sits between the engineering process of building datacenters and the theoretical consideration of abstractions of DCNs as discrete structures; that is, it is graph theory targetted towards a practical application area.

(more…)

La IP. ¿?

octubre 13, 2016

¿¿¿

entusiasmado

 

 

 

 

 

???

(more…)

2 casos de S6 (720 vértices), C2C4.

septiembre 12, 2016

Disclaimer. Entrada en construcción en la parte de actualizaciones. Puede contener errores. Estará terminada cuando desaparezca este mensaje. 

¡¡ Actualizado 19 de septiembre: ya está claro el esbozo del método de obtención de un certificado de no hamiltonicidad para los casos twisted. Ya le hemos puesto nombre y todo :-): método de la escalera. Para más detalles ver en este mismo post la actualización correspondiente al final !!.

En esta entrada mostramos las imágenes correspondientes a 2 los dos casos de S6 del tipo C2C4 (es decir, que tienen un generador de orden 2 y otro de orden 4).

Tenga el lector en cuenta que ya en estos casos, que si tienen recorridos hamiltonianos, tienen pocos, ya empieza a ser prohibitivo el  usar métodos algorítmicos. Incluso, como veremos, aplicar nuestro algoritmo, tal y como está programado ahora mismo (sin incorporar los últimos avances que hemos descrito en las últimas entradas) es prohibitivo: puede tardar semanas.

1.Caso de S6, C2C4, IAS 5, Circunferencia 10. No es ni 1-twisted ni 2-twisted.   

Comentar primero que finalmente he puesto a prueba este caso  con nuestro algoritmo y tras varios días tuve que apagarlo (ya que necesitaba usar el ordenador para otros temas) sin haber podido determinar si tiene recorridos hamiltonianos en uno de los  dos vértices finales posibles en los que puede tenerlos.

Por ello nos resulta de gran interés poder pulir los métodos que estamos describiendo en las anteriores entradas para poder determinar sus propiedades de hamiltonicidad sin necesidad de aplicar el algoritmo. O de manera alternativa También incorporar los avances señalados en las anteriores entradas al algoritmo (los que aceleran el encontrar un recorrido hamiltoniano en este tipo de casos cuando existe) para que pueda determinar esto mismo de manera más eficiente.

Nota. Es muy importante tener en cuenta que una cosa son los problemas de existencia y otra los problemas de construcción. En algunos  casos nos puede interesar conocer si un caso en concreto puede tener recorridos hamiltonianos o no, sin objetivos constructivos, sin necesitar construir un recorrido hamiltoniano en concreto aunque estos existan.

En otros casos una vez aclarado positivamente el tema de la existencia nos puede interesar construir uno, varios o todos los recorridos hamiltonianos del caso que estudiamos.

Cualquiera de estos dos problemas o de estas dos fases del mismo problema nos interesa resolverlos de la manera más eficiente posible. Tan práctico y útil para el investigador de estos problema es lo uno como lo otro.  Espero que esto lo tengan claro en la USPTO.  Fin de nota.

Como se puede ver no es ni 1-twisted ni 2-twisted y según la definición más restrictiva  sería smooth. Pero como ya como comentamos en otra entrada, no nos interesa una definición esencialista, escolástica, sino  una pragmática.  ¿ Que pasa en este tipo de casos, según el análisis que hemos presentado en  la entrada anterior ?. ¿ Es twisted o smooth en sus efectos ?. Lo dejamos como problema de momento…

La imagen se puede agrandar, para un poco  más de claridad. No está completo. Se muestra con una linea más oscura solo uno de los pares de permutaciones repetidas al expandirlo.

s6-twisted-o-smooth

Vamos a calcular las cotas teóricas de las fronteras para este caso, según el método apuntado en la entrada justo anterior. Tiene 720 vértices /ciclos de orden 4 / orden de IAS 5 = 36. Hay 720 / 5 = 144 IASes. Por lo tanto la cota de la frontera del generador 2 es  (36,108). Y para el generador de orden 4 es (72,72). ¿ No hay un patrón aquí: cuando el ciclo es de orden 2, no tiene que estar la frontera en la  mitad ?. En fin, las cotas teóricas para este caso son [C2(36, 108);C4(72,72)].

El rango que está entre las cotas teóricas de las fronteras tiene 36 pares. Es bastante más amplio que en el caso 2-twisted estudiado en la entrada anterior. Lo que no tengo claro es como funciona en este caso el mecanismo de amplificación, al no ser ni 2-twisted ni 1-twisted. No puedo dimensionarlo esta segunda pata con la que anda el método (de momento ni por aproximación) y esto es clave para determinar si el caso puede tener recorridos hamiltonianos (en este caso caminos) o no. No es fácil analizar manualmente estos casos de 720 vértices…

2. Caso de S6, IAS 6, circunferencia 3 (6 IASes). Es 2-twisted.

Este caso, pese a ser 2-twisted, tiene recorridos hamiltonianos según la investigación de Ruskey y Effler. No sabemos si se conformaron con encontrar un RH en uno de los dos vértices finales posibles que pueden serlo de un ciclo hamiltoniano o lo determinaron para los dos. Imaginamos que la primera opción es la correcta.

La pregunta es si este caso también tiene recorridos hamiltonianos en el resto de vértices finales posibles. Para ello pusimos a prueba este caso con el algoritmo para encontrar un camino hamiltoniano en uno de los vértices finales posibles y tras varios días de computo tuvimos  finalmente que apagar el programa ya que necesitábamos utilizar el ordenador para otros usos.

¿ Podemos utilizar los métodos de las  entradas anteriores para determinar si tiene recorridos hamiltonianos en todos los VFs sin necesidad de aplicar el algoritmo ?.

El caso en cuestión (no está completo).Hemos marcado en rojo las permutaciones que se repiten en el IAS nº 8 y en el nº 23. Esto demuestra que el caso  es 2-twisted:

s6-ias7

Primero es interesante comparar este caso con el caso 2-twisted de S5 que estamos comentando en otras entradas. Las propiedades de ese son S5, IAS 5, Circunferencia 6. Como el IAS es 5 se aplica el teorema de Rankin y sabemos que no puede tener recorridos hamiltonianos. Este de S6 es IAS 6, circunferencia 6 y sabemos que si tiene recorridos hamiltonianos al menos en uno de los dos vértices finales posibles. Aunque los dos son 2-twisted, por ser uno de IAS impar y el otro par no son del todo comparables.

Vamos  a determinar las cotas teóricas de las fronteras del rango de la distribución para este caso.

–C2: 720 vértices  /ciclos de orden 4 /IAS de orden 6 = 30. 720 / 6 = 120. Por lo tanto (30, 90).

–C4: 720 vértices / ciclos de orden 2 / IAS de orden 6 = 60. Por lo tanto (60,60).

Las fronteras teóricas del rango para este caso son [C2(30,90); C4(60, 60)]. Hay unos 30 pares con activaciones que podrían tener recorridos hamiltonianos.  Bastante más que en el  caso 2-twisted anterior.

Como este caso es 2-twisted, y ya tenemos referencias de casos similares (similares pero no exactamente con los mismo parámetros: el otro caso 2-twisted tiene IAS 5 y este IAS 6) más manejables, vamos a ver si es posible dimensionar la otra pata del método (lo que hemos  llamado la media) en él.

En otra entrada hemos manejado la idea de que el amplificador es constante dado el orden del IAS. Si esto se confirmase ya estaría gran parte del  trabajo realizada. Sólo habría que determinar cual es la contribución del tamaño del IAS a la diferencia en los efectos del amplificador.

(more…)

Diferencia entre un caso twisted y otro smooth (2).

septiembre 12, 2016

1.No tengo demasiado tiempo ahora para desarrollar las entradas anteriores sobre este mismo tema plenamente. Vamos a describir rápidamente la diferencia más importante, a efectos prácticos de un caso smooth (S5, sigma-tau) y otro twisted (S5, 2-twisted). Soy consciente de que el sigma  tau es C2C5 pero como se verá esto no es relevante (los escépticos al respecto tendrán que esperar a que se analice un caso C2C5 o C2C6 twisted…).

Cuando  hemos marcado el IAS de la identidad (VF ciclo) y su opuesto por el generador de orden 4, y alguno intermedio que maximice el número de IASes marcados (hay diferencias y esto se puede hacer para los dos casos) se trata de aplicar el siguiente método:

Paso 1. Hacer una lista de los ciclos que tengan al menos 2 arcos marcados.

Paso 2. Dentro de esta lista identificar que IASes tienen presentes arcos en varios de los ciclos. Si marcamos estos en un digrafo de C2C4, ya tendremos que marcar el otro arco de todos estos ciclos por el generador de orden 2 para evitar obtener ciclos de C4. Así maximizamos el nº de IASes marcados cuando tengamos que extraer las consecuencias. Puede haber varios IASes que cumplan con esta condición.  Supongamos (hipotéticamente) por ejemplo el IAS nº 2 y el IAS nº 5 y el IAS nº 7.

Paso 3. identificar algún IAS tal que al ser marcado por C2 obligue a estos tres IASes a ser marcados por el generador de orden 4. De esta manera maximizamos todavía más el número de IASes que serán marcados en cada opción, al extraer sus consecuencias. Supongamos que el IAS 9 cumple esta condición.

Entonces, elegimos la opción de marcar el IAS 9 por el generador de orden 2, esto tiene como consecuencias que los IASes 2,5 y 7 tienen que ser marcados por el generador de orden 4 y a su vez los arcos que completan estos tres ciclos tendrán que ser marcados por el generados de orden 2.

Lo importante es que al  marcar uno solo IAS obtenemos, como consecuencia muchos otros IASes marcados (llamemos a esto efecto multiplicador, por ponerle algún nombre), algunos por el generador de orden 2 y otros por el de orden 4, pero en una determinada proporción desequilibrada. Esto  se puede repetir de manera iterativa de tal manera que al final le media de la que hemos hablado en las anteriores entradas sale elevada.

La diferencia entre un caso smooth y uno  twisted es que los casos smooth, en el paso 2 no vamos a encontrar un IAS que tenga varios arcos en diferentes ciclos de los que ya tienen marcados . Por lo tanto no se puede obtener este efecto multiplicador y la media saldrá baja. Y en los casos 1-twisted y 2-twisted si se encontrarán y por lo tanto se dará el efecto multiplicador

Veamos esto con detalle (hemos realizado exactamente las mismas operaciones en los dos casos antes de realizar la lista de ciclos).

Lista de ciclos del caso 2-twisted (los datos no son hipotéticos, son reales; los números indican el número de IAS (los IASes se han numerado de manera arbitraria, un número es equivalente a un color); los signos más o menos indican si el IAS correspondiente está marcado o no; la lista incluye solo a aquellos ciclos que tienen 2 o más arcos marcados).

Una imagen del caso con los IASes marcados tal y como se han indicado. Es en esta imagen en la que  nos hemos basado para realizar las tablas siguientes. Por lo  tanto la numeración se corresponde con al del texto. El nº del IAS aparece al lado de los arcos. El IAS amarillo, el nº 18 que rodea el digrafo es el que se marca como tercera opción, por el generador de orden 2, tras marcar el IAS de la identidad y su opuesto dentro de la circunferencia  por el generador de orden 4:

s5-c2c4-twisted-22

Tabla 1.

1+,6-,7+,8-

1+,8-,10+,11-

1+,11-,12+,2-

1+,2-,3+,4-

1+,4-,5+,6-

23+,7+,6-,13-

3+,23+,9-,4-

Para simplificar hagamos ahora una lista de los IASes que no están marcados en cada ciclo.

Tabla 2 derivada de la tabla 1 simplificando.

6,8

8,11

11,2

2,4

4,6

6,13

9,4

Vemos que el IAS 6 tiene arcos en 3 ciclos, al igual que el 4. El 8,11 y 2 tienen arcos en dos ciclos. Por lo tanto 6,4,8,11 y 2 son los IASes de nuestro interés.

El siguiente paso, el Paso 3, sería identificar IASes que estén unidos al 6 y al 4 y posiblemente a alguno de los otros 3. Si existe, se selecciona el que maximice el numero de IASes. En el caso en concreto hay varias posibilidades: el IAS nº 24 por ejemplo conecta con el 6 y con el 11 y con otros cuatro, ninguno de ellos marcado; el IAS 13 conecta con el 2, con el 17 y con otros 4 uno de ellos ya marcado etc…. Habrá que seleccionar la opción que conecte con más de ellos y si es posible que tengan presentes más arcos en diferentes IASes.

El lector podrá comprobar como el que suceda este fenómeno depende de la propiedad de ser retorcido o twisted.

Lista de ciclos para el caso Sigma-Tau (caso real, nos ceñimos a la tabla 2; se han obtenido tras marcar el IAS de la identidad y su opuesto por el generador de orden 4, y marcando como tercera opción un IAS seleccionándolo para que maximizase el nº de IASes marcados).

Por cierto, tras consultar en mi base de datos, confirmo que este caso Sigma-Tau tiene recorridos hamiltonianos en todos los vértices finales posibles.

La imagen (idem anterior):

s5-sigma-tau-22

Tabla 2 (ninguno de los IASes que aparecen está marcado).

5,6,24

10,11,2

8,28,16

12,27,20

No hay ninguno repetido. Es importante señalar que en realidad si hay varios ciclos tal que un mismo IAS pasa por ellos pero en todos ellos hay un arco de orden 4 marcado como que no se debe de marcar (es decir su correspondiente IAS está ya marcado por el generador de orden 2) y por lo tanto este ciclo no se puede compltar, que es lo que nos preocupa. Estos ciclos con una arco marcado como que no se debe de marcar no cuentan.

Como había otro IAS candidato a la tercera opción hemos repetido el proceso para varios IASes diferentes, para todos los candidatos y estas son las tablas de tipo 2 que se obtienen:

2,4,5

10,24,9

20, 19, 8

12,16, 25

De nuevo, ninguno repetido, como puede comprobar el lector. En el caso Sigma-Tau, como en todos los smooth, no hay efecto multiplicador y por lo tanto no existe el mismo obstáculo que en los twisted a la hora de que pueda haber recorridos hamiltonianos.

De la misma manera, seguramente en los smooth, seguramente no será posible encontrar un IAS en el paso 3 que sea más ventajoso que el resto. Cada opción en los casos smooth es mucho más independiente que en los casos twisted.

2. Lo anterior obviamente no es una demostración de que el caso 2-twisted no puede tener recorridos hamiltonianos. Los parámetros del caso analizado 2-twisted son S5, C2C4, IAS5 y circunferencia 6. como el IAS es de orden 5, tiene 24 IASes y por lo tanto la distribución recorre desde 0 IASes activados por el generador de orden 2 y 24 activados por el de orden 4, es decir (0,24) al otro extremo (24,0). Interesa determinar un método rápido que nos permita identificar las fronteras, es decir entre que intervalos de pares [(0,24); (x,y)] y [(w,z); (24,0)] sabemos que no pueden existir RHs. Ahora mismo, para este caso en concreto no me parece evidente determinar esto salvo los extremos extremos, pero igual es que es última hora del día…

Los parámetros del caso Sigma-Tau son S5, C2C5, IAS4 y circunferencia 6. Tiene por lo tanto 30 IASes y el rango de la distribución recorre (30,0) a (0,30).  Idem anterior.

Actualización día siguiente.

El método más directo para determinar acotar la frontera es el siguiente (vale para cualquier caso). Nos conformamos con acotar la frontera.  Pienso que será suficiente para lo que nos interesa.

Frontera para el generador de orden 2.

El  método (que hoy me parece obvio) es el siguiente:

–Obtenemos primero el nº de ciclos de orden 4 que tiene el caso. Para el 2-twisted hay 120/4 = 30.

–Si queremos que no aparezca un ciclo de estos con todos los arcos marcados, tiene que haber en cada uno de ellos al menos un arco desactivado por el generador de orden 4. Y por lo tanto el IAS de ese arco tendrá que ser activado por el generador de orden 2. Por lo tanto tiene que haber al menos 30 arcos marcados por el generador 2.

–Como el IAS es de orden 5, cada IAS tiene 5 arcos del generador 2. Para obtener la cota dividimos el número obtenido anteriormente, 30, que indica el número de arcos que deberán de ser activados por el generador 2, por el número de arcos del generador 2 que contanga un IAS, que es equivalente al orden del IAS, en este caso 5. Es decir 30/5 = 6. La cifra obtenida, 6 en este caso nos da el número de IASes mínimo que tendremos que marcar para que no haya un ciclo de orden 4.

¿ Podemos concluir que tiene que haber al menos 6 IASes marcados por el generador 2 para que pueda haber recorridos hamiltonianos  y que por lo tanto (6,18) es la frontera para el generador de orden 2 ?. Es decir que menos de 6 IASes marcados por el generador 2, no puede haber recorridos hamiltonianos, y más de 6 IASes sí puede haberlos.

No lo tengo claro: ¿ no puede haber algún ciclo que contenga arcos de dos de los 6 IASes diferentes y por lo tanto aunque marquemos 6 IAses todavía habría ciclos de orden 4 sin ningún arco marcado como que no puede ser activado ? . Hagamos la pregunta traducida a un lenguaje experimental: en el caso 2-twisted ¿ podemos seleccionar entre los 24 IASes 6 de ellos tal que al activarlos por el generador de orden 2 todos los ciclos de orden 4 tengan un arco de orden 4 desactivado ?.

¿ Y en el caso Sigma-Tau ?. Apliquemos este método al caso Sigma-Tau para ver cuantos IASes tendríamos que marcar. 120/5= 24 ciclos de orden 5. Hay que marcar 24 arcos por el generador de orden 2. El IAS es de orden 4 y por lo tanto cada IAS tiene 4 arcos de orden 2. 24/4=6. También en este caso hay que marcar 6 IASes entre 30. Aquí tenemos más espacio, lo cual ya es un dato….

Tras estudiar este tema para el caso Sigma Tau (de manera no sistemática, no he agotado todas las posibilidades, pero no hay duda) se puede concluir que para este caso no existen 6 IASes independientes entre los 30.

La segunda conclusión es que cuando no existe este número mínmo de IASes independientes, al haber repeticiones, hay que marcar más IASes que los que indica este límite teórico para que todos los ciclos de orden 4 tengan al menos un arco desactivado.

Por lo tanto este método, que se puede aplicar de manera muy rápida cuando conocemos los parámetros, nos sirve para encontrar una cota inferior de la frontera.   En algunos casos, conocer esta cota inferior será suficiente para poder demostrar que el caso en cuestión no puede contener recorridos hamiltonianos.

La fórmula para encontrar esta cota inferior es:

Cota frontera = (Orden del digrafo / orden del ciclo) / orden del IAS. 

Calculemos las dos cotas para el caso Sigma-Tau y para el 2-twisted.

Sigma-Tau: [C2(6,24);C4(15,15)]. Es decir menos o 6 IAses marcados por C2, no podría haber recorridos hamiltonianos; menos o 15 IASes marcados por C4 tampoco podría haber recorridos hamiltonianos. La situación con respecto a los pares contenidos entre estas fronteras es indeterminada.

2-Twisted: [C2(6,18); C4(12,12)]. Idem anterior. Aquí vamos a concretar: podría haber recorridos hamiltonianos con 7 IASes marcados por el generador de orden 2 y 17 IASes marcados por el generador de orden 4. Con (8,16), con (9,15), con (10,14) y con (11,13). El rango entre las cotas de las fronteras es menor que en el caso Sigma-Tau.

Los conceptos y métodos que hemos expuesto en las entradas anteriores lo que permitirían (el tema está en investigación) es demostrar que en los casos twisted, por el fenómenos de multiplicador o amplificación que la propiedad twisted provoca o permite, no son posibles activaciones “coherentes” que nos lleven al rango que está entre las cotas de las fronteras teóricas. Cualquier activación posible dentro de este rango que intente evitar ciclos no hamiltonianos, hará que acabemos en activaciones por debajo de las cotas teóricas de la frontera.

Comentar que en todas las últimas entradas no estamos teniendo en cuenta consideraciones de complejidad computacional. Pero cuando hayamos aclarado todas estas dudas estas consideraciones serán clave: encontrar test rápidos  y que utilicen poca memoria de retorcimiento.

Fin de actualización.

HPC. Top 500. El sistema Sunway TaihuLight es nº 1.

septiembre 2, 2016

Sunway TaihuLight is the new No. 1 system with 93 petaflop/s (quadrillions of calculations per second) on the LINPACK benchmark.

Fuente, la página web del TOP500.

Como siempre en las últimas ediciones del actualizado bianualmente ranking TOP500, informamos con retraso, en esta ocasión de un par de meses o más, sobre las novedades en su última edición de junio de 2016.

Desarrollamos el tema en tres puntos: el primero con enlaces a detalles técnicos del sistema; el segundo con información sobre los 6 centros de supercomputación en China y su localización y el tercero con algunos enlaces que contienen consideraciones geopolíticas sobre estos avances en la tecnología de la R.P. China.

1.La mayor novedad del ranking es que ahora el sistema nº1, que da nombre a la entrada, es un nuevo sistema chino, que adelanta así a al también sistema chino Tianhe-2 que ha reinado en las primeras posiciones en los 2 o 3 últimos años.

(more…)